HDU-1024 Max Sum Plus Plus(DP)
题意：可以认为是最大和子序列的进化版, 要求从一串序列中取出若干段, 使得这几段的和最大。
思路：
可以先推出来一个二维的转移方程式：
dp[i][j] = max(dp[i-1][j]+num[i], max(dp[t][j-1]+num[i]); (其中 j-1 <= t <= i-1)
表示从前i个数中取j个段能够取得的最大和，并要求最后一个段包含num[i];
题目给的序列长度为1e6，二维肯定爆，所以再考虑优化空间。
分析上面二维方程式，发现共取j段的dp[i]只会和dp[i-1]和(j-1)段的dp[i]有关。
所以增加一个pre数组存储上一层(j-1)的状态即可。
细节请看代码,
#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstdio>
#define LL long long
using namespace std;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1000005;
LL dp[maxn], pre[maxn];
int num[maxn];
int n, m;
LL ans, mmax;
int main()
{
while(~scanf("%d %d", &m, &n))
{
for(int i = 1; i <= n; ++i)
{
scanf("%d", &num[i]);
dp[i] = pre[i] = 0;
}
dp[0] = pre[0] = 0;
for(int j = 1; j <= m; ++j)
{
mmax = -inf; //用mmax寻找pre(j-1)~pre(i-1)中的最大值
for(int i = j; i <= n; ++i)
{
mmax = max(mmax, pre[i-1]);
dp[i] = max(dp[i-1], mmax) + num[i];
}
for(int i = j; i <= n; ++i) pre[i] = dp[i];
}
ans = -inf;
for(int i = m; i <= n; ++i) ans = max(ans, dp[i]);
printf("%lld\n", ans);
}
return 0;
}继续加油~