HDU - 1024 Max Sum Plus Plus

https://vjudge.net/problem/HDU-1024

题意：将一个长度为n的序列，分成m段不相交叉的子段，使得他们的和最大

输入： m，n ，接下来n个数

设：

dp[i][j]:必须选第i个数，前i个数分为j段最大值

mxx[i][j]：dp[1][j]~dp[i][j]的最大值

转移方程：

dp[i][j]=max(dp[i-1][j]+a[i],mxx[i-1][j-1]+a[i])

其中a[i]为第i个数

转移方程的意思为：对于第i个数，要么将其归入上一段中，要么新开一段

#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 7;
int dp[maxn], mxx[maxn];
// dp[i][j]:必须选第i个书，前i个数分为j段最大值
// mxx[i][j]：dp[1][j]~dp[i][j]的最大值
// 方程：dp[i][j]=max(dp[i-1][j]+a[i],mxx[i-1][j-1]+a[i])
int n, m;
int main() {
 while (cin >> m >> n) {
  int inp;
  memset(dp, -INF, sizeof(dp));
  memset(mxx, -INF, sizeof(mxx));
  dp[0] = mxx[0] = 0;
  int ans = -INF;
  for (int i = 1; i <= n; i++) {
   scanf("%d", &inp);
   for (int j = m; j; j--) {
    dp[j] = max(dp[j], mxx[j - 1]) + inp;
    mxx[j] = max(mxx[j], dp[j]);
   }
   ans = max(ans, dp[m]);
  }
  printf("%d\n", ans);
 }
 return 0;
}