序列歸并-有解無憂

Description

Alice 和Bob 正在對兩個序列a1, a2,..., an 和b1, b2,...,bm 進行操作，
Alice 首先需要將它們歸并成一個長度為n + m 的序列c₁,c₂,...,c_n+m，即將序列a 和b 合并成一個序列c，但不改變a 和b 的順序，顯然可能有許多許多種不同的歸并結果，
Bob 需要在Alice 完成歸并之后，選擇一對l,r，滿足1 ≤ l ≤ r ≤ n + m，并使得score = c_l+ c_l+1 + c_l+2 + ...+ c_r−1 + c_r盡可能地大，

不同的歸并結果以及不同的選擇l,r 的方式都會使得最后score 的值不盡相同，請問score 最多能達到多少呢？

Input

第一行包含一個正整數T(1 ≤ T ≤ 10)，表示測驗資料的組數，
每組測驗資料第一行包含兩個正整數n,m(1 ≤ n,m ≤ 100000)，分別表示序列a 和序列b 的長度，
第二行包含n 個整數a₁, a₂,..., a_n(−10⁹ ≤ a_i ≤ 10⁹)，
第三行包含m 個整數b₁,b₂,..., bm(−10⁹ ≤ b_i ≤ 10⁹)，
輸入資料保證a 和b 中至少有一個正數，

Output

對于每組測驗資料，輸出一行一個整數，即score 的最大值，

Sample Input

1 2 3 1 5 3 -1 -1

Sample Output

HINT

一種可能的歸并結果是c = [1, 3, 5,−1,−1]，選擇l= 1, r = 3，則score = c₁ + c₂ + c₃ = 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 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61740.html

標籤：C++

上一篇：C++ Primer 抄書筆記（一）

下一篇：STL中_Rb_tree的探索