HDU 1024 Max Sum Plus Plus

 1 /*
 2   状态转移方程：dp[i][j] (从前i个数选出j段 和的最大值)
 3   dp[i][j] = max(dp[i-1][j], max(dp[k][j-1])) + num[i]; (j-1 <= k <= i-1)
 4   目标状态应该是 dp[n-1][m] 也就是 dp2[m]
 5  */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 using namespace std;
11 #define inf 0x4f4f4f
12 #define maxn 1000010
13 
14 int dp1[maxn], dp2[maxn]; // dp1表示dp[][j-1] dp2表示dp[][j]
15 int num[maxn]; //输入数组
16 
17 int main() {
18     int m, n;
19     while (cin >> m >> n) { // m = 0 or n= 0 时 ans = 0;
20 
21         for (int i=1; i<=n; ++i) {
22             cin >> num[i];
23             dp1[i] = 0; //初态 j = 0时。
24             dp2[i] = 0;
25         }
26         dp1[0] = 0;
27         dp2[0] = 0;
28 
29         int anstemp = -inf;
30         for (int i=1; i<=m; ++i) { // 选m组 这是第二维的j 从1 到m 选的段数从1到m。
31             anstemp = -inf; // 记录j-1 即 选择段数为i-1时 的最大值
32             for (int j=i; j<=n; ++j) { // 从前j个数里选、dp1[j-1]记录的是选择i段是 0到j-1的最大值
33                 dp2[j] = max(dp2[j-1], dp1[j-1]) + num[j]; // 现在的问题是我不知道怎么更新或者保存 dp1[j-1] 是从选前1个数到选前j-1个数 的最大值。
34                 dp1[j-1] = anstemp;  // 开始以为只是单纯的dp1[j-1]。实际上是j-1段的时候。也就是上一个循环的。
35                 anstemp = max(dp1[j-1], dp2[j]);
36             }
37         }
38         //cout << anstemp << endl; // 输出如果是dp2[n]呢。WA ...dp2[n]最后结果保存的是从前n个数选择m段 的最大值、anstemp和dp1[n]保存的是从选1 段数到选m段。的最大值。
39         //只保存到了dp[n-1]、可知antemp是ans.或者
40         cout << max(dp1[n-1], dp2[n]) << endl;
41     }
42     return 0;
43 }