【HDOJ】1244 Max Sum Plus Plus Plus

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 #define MAXN 1020
 9 #define MAXM 35
10 #define INF 0xfffff
11 
12 int dp[MAXM][MAXN];
13 int l[MAXM];
14 int sums[MAXN];
15 
16 int main() {
17     int n, m, sum;
18     int i, j, k, tmp;
19 
20 #ifndef ONLINE_JUDGE
21     freopen("data.in", "r", stdin);
22     freopen("data.out", "w", stdout);
23 #endif
24 
25     while (scanf("%d",&n)!=EOF && n) {
26         scanf("%d", &m);
27         for (i=1; i<=m; ++i)
28             scanf("%d", &l[i]);
29         sums[0] = 0;
30         for (i=1; i<=n; ++i) {
31             scanf("%d", &tmp);
32             sums[i] = sums[i-1] + tmp;
33         }
34         sum = 0;
35         memset(dp, 0, sizeof(dp));
36         for (i=m; i>0; --i) {
37             sum += l[i];
38             for (j=n-sum+1; j>0; --j) {
39                 dp[i][j] = max( dp[i][j+1], dp[i+1][j+l[i]]+(sums[j+l[i]-1]-sums[j-1]) );
40             }
41         }
42         printf("%d\n", dp[1][1]);
43     }
44 
45     return 0;
46 }