会做一段子序列的最大和,但没想到M段子序列的最大和这么难,完全不会啊!
看了题解几乎清一色都是这种做法,方法和一段子序列的思路完全不一样啊。。。
dp[j]表示以第j个元素结尾的i个子段的最大和,包含a[j]。
pre[j]表示第j个元素以前元素的i个子段的最大和,不包含a[j]。
temp用于存放临时最大值。
真的很不好凭空理解,只好写下来了。
可以看出,当前一步的temp值和前一步的并没有关系,而且也不储存,储存的是dp和pre数组的值,且每一次遍历i都刷新一次数组。这是什么意思呢?求一个序列的M段子序列和,不可能一段一段求出来再加起来,只能是一步步往出推,使答案由模糊变清晰的过程。至于相邻两个数组有什么关系,我反正看不出来,只能说是递归的多元版吧。普通的递归处理的都是一维数组,而本题却是同时处理dp,pre两个数组外加一个temp(T T握日。。。逼格瞬间高了起来)。滚动数组我就不说了,但凡是个动态规划就会这样处理数组节省空间,见怪不怪的。。。
核心代码我还没有理解透彻,透彻了再更,免得贻笑大方。。。
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;
const int INF = 1000000000;
int main()
{
// freopen("in.txt", "r", stdin);
int i, j, m, n, temp;
int a[N], dp[N], pre[N];
while(~scanf("%d%d", &m, &n))
{
memset(dp, 0, sizeof(dp));
memset(pre, 0, sizeof(pre));
for(i = 1; i <= n; i ++)
scanf("%d", &a[i]);
for(i = 1; i <= m; i ++)
{
temp = -INF;
for(j = i; j <= n; j ++)
{
dp[j] = max(dp[j - 1], pre[j - 1]) + a[j];
pre[j - 1] = temp;
temp = max(temp, dp[j]);
}
}
printf("%d\n", temp);
}
return 0;
}