/*超时。题意:输出m个子序列和的最大值思路:动态规划 + 滑动数组d[m][j] = max(d[m][j - 1] + e[j], max(d[m - 1][k] + e[j]) | k ∈ [m -1, j)).表示前j个序列分割成m组,最大序列和因为状态方程中只用到d[m]和d[m - 1]两个状态,所以只需要一个二维数组即可。优化:至于max(d[m - 1][k] + e[j])过程,可以直接在d[0][j]中存储在j之间分割成m - 1的最大值。这样状态转移方程变为d[1][j] = max(d[1][j - 1] + e[j], d[0][j - 1] + e[j]);*/#include <iostream>using namespace std;const int nMax = 1000010;const int MIN = -0x7fffffff;int e[nMax];__int64 d[2][nMax];int m, n;int main(){ //freopen("e://data.txt", "r", stdin); while(scanf("%d%d", &m, &n) != EOF) { for(int i = 1; i <= n; ++ i) scanf("%d", &e[i]); memset(d, 0, sizeof(d)); for(int i = 1; i <= m; ++ i) { for(int j = i; j <= n; j ++) { /* for(int k = m - 1; k < j; k ++) { d[1][j] = max(d[0][k] + e[j], d[1][j]); } */ d[1][j] = max(d[0][j - 1] + e[j], d[1][j]); d[1][j] = max(d[1][j - 1] + e[j], d[1][j]);//临界时候已经被包含在内,所以不需要再另外做处理。 } for(int j = i; j <= n; ++ j) { d[0][j] = max(d[0][j - 1], d[1][j]); d[1][j] = MIN; } } /* int _max = 0; for(int i = m; i <= n; ++ i) _max = max(_max, d[0][i]); */ printf("%I64d\n", d[0][n]); } return 0;}
分享到:
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码
HDOJ使用指南——公开版.docHDOJ使用指南——公开版.docHDOJ使用指南——公开版.doc