HDU 1024 Max Sum Plus Plus

 题目链接：Max Sum Plus Plus

 大意：给出m n 和n个数、然后问在n个数里找m组数 求和 问最大值是多少。

 思路 想从前i个数 找出m组，第i个数要么是自己一组，要么就是和num[i-1]一组，要么就是自己一组。可得转移方程。

 代码实现的时候，不知道怎么更新dp[][j-1]即dp1[]。后来明白发现这个方法太神奇了....

/*
  状态转移方程：dp[i][j] (从前i个数选出j段 和的最大值)
  dp[i][j] = max(dp[i-1][j], max(dp[k][j-1])) + num[i]; (j-1 <= k <= i-1)
  目标状态应该是 dp[n-1][m] 也就是 dp2[m]
 */

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define inf 0x4f4f4f
#define maxn 1000010

int dp1[maxn], dp2[maxn]; // dp1表示dp[][j-1] dp2表示dp[][j]
int num[maxn]; //输入数组

int main() {
    int m, n;
    while (cin >> m >> n) { // m = 0 or n= 0 时 ans = 0;

        for (int i=1; i<=n; ++i) {
            cin >> num[i];
            dp1[i] = 0; //初态 j = 0时。
            dp2[i] = 0;
        }
        dp1[0] = 0;
        dp2[0] = 0;

        int anstemp = -inf;
        for (int i=1; i<=m; ++i) { // 选m组 这是第二维的j 从1 到m 选的段数从1到m。
            anstemp = -inf; // 记录j-1 即 选择段数为i-1时 的最大值
            for (int j=i; j<=n; ++j) { // 从前j个数里选、dp1[j-1]记录的是选择i段是 0到j-1的最大值
                dp2[j] = max(dp2[j-1], dp1[j-1]) + num[j]; // 现在的问题是我不知道怎么更新或者保存 dp1[j-1] 是从选前1个数到选前j-1个数 的最大值。
                dp1[j-1] = anstemp;  // 开始以为只是单纯的dp1[j-1]。实际上是j-1段的时候。也就是上一个循环的。
                anstemp = max(dp1[j-1], dp2[j]);
            }
        }
        //cout << anstemp << endl; // 输出如果是dp2[n]呢。WA ...dp2[n]最后结果保存的是从前n个数选择m段 的最大值、anstemp和dp1[n]保存的是从选1 段数到选m段。的最大值。
        //只保存到了dp[n-1]、可知antemp是ans.或者
        cout << max(dp1[n-1], dp2[n]) << endl;
    }
    return 0;
}