HDU 1024 Max Sum Plus Plus

2019-11-08 19:33:41

字体：大中小

来源：转载

供稿：网友

题意：求m个不相交区间段的和的和的和最大思路：动态规划分析：dp[i][j]表示以a[j]结尾的i个区间段的和的最大和；状态转移方程：dp[i][j]=max(dp[i][j-1]+a[j],dp[i-1][k]+a[j]) dp[i-1][k]=max(dp[i-1][i~n]) 即划分成i-1个区间分别以（a[i~n]）为结尾中的最大值。（当划分成i个区间的时候前1-i个数字必定在一个区间里） dp[i][j]可以表示为和上一个区间相连即dp[i][j-1]+a[j]或者自己独立为一个区间即dp[i-1][k]+a[j]；

#include<iostream>#include<string>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>#include<cmath>#include<math.h>#include<vector>#include<map>#include<stack>using namespace std;typedef long long ll;#define INF 0x7fffffffint a[1000005];int dp[1000005];int PRe[1000005];int main(){ int n, m; while (scanf("%d %d", &m, &n) != EOF) { int maxx; memset(a, 0, sizeof(a)); memset(dp, 0, sizeof(dp)); memset(pre, 0, sizeof(pre)); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= m; i++) { maxx = -INF; for (int j = i; j <= n; j++) { dp[j] = max(dp[j - 1] + a[j], pre[j - 1] + a[j]); pre[j - 1] = maxx;//记录前面的最大值 maxx = max(dp[j], maxx);//更新到当前的最大值 } } printf("%d/n", maxx); } return 0;}

链接：http://acm.hdu.edu.cn/showproblem.php?pid=1024

上一篇：beego MySQL数据库连接池

下一篇：比较成绩