题目：XJOI335
传送门 [ >XJOI<]
重要提示：您的膜法等级必须达到3级6段才可使用本传送门，否则您会被小猫痛扁
因为博主太懒，不提供题面(QAQ)...
很容易想到使用DP,设f[i][j]为第i个段,第i-1段以j-1为终点的最大可能和。
于是引出递推式:f[i][j] = max(f[i-1][k]) 其中k枚举且k<j。
然后优化DP，使用一个数组来保存max(f[i-1][k])的值省去枚举。
发现该数组必须使用交替的方式来保证需要的值不被覆盖。
最后一步发现f数组的第一维可以省去，空间不会溢出，得解！
附上一段垃圾代码：
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
ll p[],f[],Max[][];
int main()
{
int n, m, k, i;
scanf("%d %d %d",&n,&m,&k);
for (i=;i<=n;i++)scanf("%lld",&p[i]);
ll max_ans=;
for (i=;i<=k;i++){
int j;Max[][] = ;
for (j=(i-)*m+;j<=(n-m+);j++){
ll tmp = ;
for (int K=;K<m;K++)tmp+=p[j+K];
if (j - m > )f[j]=Max[][j - m]+tmp;else f[j]=tmp;
if (f[j]>Max[][j-]||j==((i-)*m+))Max[][j]=f[j]; else Max[][j]=Max[][j-];
if (i==k&&f[j]>max_ans)max_ans=f[j];
}
memset(Max[],,sizeof(Max[]));
for (j=(i-)*m+;j<=(n-m+);j++)Max[][j]=Max[][j];
}
printf("%lld",max_ans);
return ;
}
别问我为什么要压行，XJ老是拦截(QWQ)，我也没办法啊。