序列归并

0
10

Description

Alice 和Bob 正在对两个序列a1, a2,…, an 和b1, b2,…,bm 进行操作。
Alice 首先需要将它们归并成一个长度为n + m 的序列c1,c2,…,cn+m。即将序列a 和b 合并成一个序列c,但不改变a 和b 的顺序。显然可能有许多许多种不同的归并结果。
Bob 需要在Alice 完成归并之后, 选择一对l,r, 满足1 ≤ l ≤ r ≤ n + m, 并使得score = cl+ cl+1+ cl+2+ …+ cr−1+ cr尽可能地大。

不同的归并结果以及不同的选择l,r 的方式都会使得最后score 的值不尽相同,请问score 最多能达到多少呢?

Input

第一行包含一个正整数T(1 ≤ T ≤ 10),表示测试数据的组数。
每组测试数据第一行包含两个正整数n,m(1 ≤ n,m ≤ 100000),分别表示序列a 和序列b 的长度。
第二行包含n 个整数a1, a2,…, an(−109≤ ai≤ 109)。
第三行包含m 个整数b1,b2,…, bm(−109≤ bi≤ 109)。
输入数据保证a 和b 中至少有一个正数。

Output

对于每组测试数据,输出一行一个整数,即score 的最大值。

Sample Input

1
2 3
1 5
3 -1 -1

Sample Output

9

HINT

一种可能的归并结果是c = [1, 3, 5,−1,−1],选择l= 1, r = 3,则score = c1+ c2+ c3= 9。


这道题wa了好多次,不知道是哪边有问题,我一开始还以为是纯粹地求序列最大和,然后看了学长的代码之后,才发现这道题是dp,阅历太少啊

代码

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[100005],b[100005];
 5 ll he(ll a[],ll n)
 6 {
 7     ll i,tmp=0,t=0;
 8     for(i=0;i<n;i++)
 9     {
10         tmp+=a[i];
11         if(tmp>t)
12         {
13             t=tmp;
14         }
15         else if(tmp<0)
16         {
17             tmp=0;
18         }
19     }
20     return t;
21 }
22 int main()
23 {
24     ll repeat;
25     scanf("%lld",&repeat);
26     ll i;
27     while(repeat--)
28     {
29         ll n,m;
30         scanf("%lld%lld",&n,&m);
31         for(i=0;i<n;i++)
32         {
33             scanf("%lld",&a[i]);
34         }
35         for(i=0;i<m;i++)
36         {
37             scanf("%lld",&b[i]);
38         }
39         ll s=he(a,n)+he(b,m);
40         printf("%lld\n",s);
41     }
42 }

<

发布回复

请输入评论!
请输入你的名字