题意:把长度为n的序列分成k个m长的连续小序列,这些连续小序列的和最大是多少。
解法:显然DP。
定义: dp[i][j] 为前 i 个元素分成j个m端,且 i 是第j个的末尾的最大和。
那么有: dp[i][j] = max(dp[i-1][j], dp[i-m][j-1]+sum[i]-sum[i-m])
5000*5000的空间,是有点大。。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define lll __int64
using namespace std; lll dp[][];
lll a[],sum[]; int main()
{
int n,m,k;
int i,j;
while(scanf("%d%d%d",&n,&m,&k)!=EOF)
{
sum[] = ;
for(i=;i<=n;i++)
{
scanf("%I64d",&a[i]);
sum[i] = sum[i-]+a[i];
}
for(i=;i<=n;i++)
for(j=;j<=k;j++)
dp[i][j] = ;
for(i=m;i<=n;i++)
{
dp[i][] = max(dp[i][],dp[i-][]);
for(j=;j<=k;j++)
{
dp[i][j] = max(dp[i][j],dp[i-][j]);
dp[i][j] = max(dp[i][j],dp[i-m][j-]+sum[i]-sum[i-m]);
}
}
cout<<dp[n][k]<<endl;
}
return ;
}