HDU 1244 Max Sum Plus Plus Plus

虽然这道题看起来和 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 = 1000 + 10;
int a[maxn], sum[maxn], len[22], dp[22][maxn];

int main(void)
{
    #ifdef LOCAL
        freopen("1244in.txt", "r", stdin);
    #endif

    int n, m;
    while(scanf("%d", &n) == 1 && n)
    {
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i)
            scanf("%d", &len[i]);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        sum[0] = 0;
        for(int i = 1; i <= n; ++i)
            sum[i] = sum[i - 1] + a[i];
        memset(dp, 0, sizeof(dp));
        for(int i  = 1; i <= m; ++i)
        {
            for(int j = 1; j < len[i]; ++j)
                dp[i][j] = dp[i][j-1];
            for(int j = len[i]; j <= n; ++j)
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-len[i]] + sum[j] - sum[j-len[i]]);
        }
        printf("%d
", dp[m][n]);
    }
    return 0;
}