动态规划|HDU 1024 Max Sum Plus Plus 动态规划|算法刷题之旅

题目链接：[kuangbin带你飞]专题十二基础DP1 A - Max Sum Plus Plus
题意

给n个数，将其分为m部分，各部分之间不能有交叉重叠，求最大和

思路

【动态规划|HDU 1024 Max Sum Plus Plus】dp[i][j]表示前j个数分为i部分的最大和，则
dp[i][j] = max(dp[i][j-1] + a[j], dp[i-1][k] + a[j]) i-1<=k<=j-1
前者是将第j个数加入到第i部分，后者是将第j个数做为第i部分的第一个数。
两个关键点

因为题目n值范围过大，显然二维数组不行。
而d[i][x]只与d[i-1][x]有关，所以可以将其降低至一维。
即dp[j]表示前j个数所分段后的和。

因为dp[i-1][k]的取值需要一重循环，极有可能导致超时，所以使用数组max存储当前层的最大值，以供下一层求值使用。
dp[j] = max(dp[j-1] + a[j], max[j-1] + a[j])

代码

#include #include #include #include #include #include #include using namespace std; const int N = 1000009; int dp[N], a[N], mx[N]; int main() { int n, m; while(~scanf("%d%d", &m, &n)) { for(int i=1; i<=n; i++) scanf("%d", &a[i]); memset(mx, 0, sizeof(mx)); dp[0] = 0; int mmax; for(int i=1; i<=m; i++) { mmax = -100000000; for(int j=i; j<=n; j++) { dp[j] = max(dp[j-1]+a[j], mx[j-1]+a[j]); mx[j-1] = mmax; mmax = max(mmax, dp[j]); } } printf("%d\n", mmax); } return 0; }