序列归并
2020-02-19 16:00:48来源:博客园 阅读 ()
序列归并
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 -1Sample Output
9HINT
一种可能的归并结果是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 }
原文链接:https://www.cnblogs.com/jackwang-sparrow/p/12333159.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 整数去重 2020-02-23
- 算法训练 拦截导弹(最长递增子序列和最长递减子序列问题, 2020-02-20
- MergeSort(归并排序)原理及C++代码实现 2020-01-14
- P1637 三元上升子序列 2020-01-07
- P1637 三元上升子序列 2020-01-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash