虽然这道题看起来和 HDU 1024 Max Sum Plus Plus 看起来很像，可是感觉这道题比1024要简单一些
前面WA了几次，因为我开始把dp[22][maxn]写成dp[maxn][22]了，Orz
看来数组越界不一定会导致程序崩溃，也有可能返回一个错误的结果
dp[i][j]表示前j个数构成前i段所得到的最大值
状态转移方程：
dp[i][j] = max{dp[i][j-1], dp[i-1][j-len[i]] + sum[j] - sum[j-len[i]]}
分别对应着不取第i个数和取第j个数及其之前相邻的共len[i]个数作为第i段加上之前的数构成i-1段构成的最大值
//#define LOCAL
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std; const int maxn = + ;
int a[maxn], sum[maxn], len[], dp[][maxn]; int main(void)
{
#ifdef LOCAL
freopen("1244in.txt", "r", stdin);
#endif int n, m;
while(scanf("%d", &n) == && n)
{
scanf("%d", &m);
for(int i = ; i <= m; ++i)
scanf("%d", &len[i]);
for(int i = ; i <= n; ++i)
scanf("%d", &a[i]);
sum[] = ;
for(int i = ; i <= n; ++i)
sum[i] = sum[i - ] + a[i];
memset(dp, , sizeof(dp));
for(int i = ; i <= m; ++i)
{
for(int j = ; j < len[i]; ++j)
dp[i][j] = dp[i][j-];
for(int j = len[i]; j <= n; ++j)
dp[i][j] = max(dp[i][j-], dp[i-][j-len[i]] + sum[j] - sum[j-len[i]]);
}
printf("%d\n", dp[m][n]);
}
return ;
}
代码君