虽然这道题看起来和 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段构成的最大值

 

1 //#define LOCAL 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6  7 const int maxn = 1000 + 10; 8 int a[maxn], sum[maxn], len[22], dp[22][maxn]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("1244in.txt", "r", stdin);14     #endif15 16     int n, m;17     while(scanf("%d", &n) == 1 && n)18     {19         scanf("%d", &m);20         for(int i = 1; i <= m; ++i)21             scanf("%d", &len[i]);22         for(int i = 1; i <= n; ++i)23             scanf("%d", &a[i]);24         sum[0] = 0;25         for(int i = 1; i <= n; ++i)26             sum[i] = sum[i - 1] + a[i];27         memset(dp, 0, sizeof(dp));28         for(int i  = 1; i <= m; ++i)29         {30             for(int j = 1; j < len[i]; ++j)31                 dp[i][j] = dp[i][j-1];32             for(int j = len[i]; j <= n; ++j)33                 dp[i][j] = max(dp[i][j-1], dp[i-1][j-len[i]] + sum[j] - sum[j-len[i]]);34         }35         printf("%d\n", dp[m][n]);36     }37     return 0;38 }