题解是看的这里的：
http://www.acmerblog.com/hdu-1024-Max-Sum-Plus-Plus-1276.html
当前这个状态是dp[i][j]，i 表示当前的段，j表示前j个数组成了当前的这i个段的最大值，而且a[j]在最后一个段中
- 状态dp[i][j]可以从dp[i][j-1]转移过来，表示第j个数字正好可以和 i 个段的前j-1个数字相加的和是当前所在状态中最大的
- 状态dp[i][j]可以从dp[i-1][j-1]转移过来，表示第 j 个数字正好可以成为第 i 个段，并且使得和i-1个段相加的和是当前所有状态中最大的
注意在第26行和第30行代码更新dp以后，其含义变成前i个段前j个数构成和的最大值，而a[j]并不一定要在这些段中，反正从这个状态转移过去的时候a[j+1]自成一段，与a[j]无关
最最头疼的就是DP过程中状态的含义会发生变化，Orz
现在看来kuangbin大神说的到清楚一些，不过他的代码的变量命名方式是在不敢恭维，=_=||
http://www.cnblogs.com/kuangbin/archive/2011/08/04/2127085.html
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1000000 + 10, INF = (1 << 30); 9 int dp[2][maxn], a[maxn], m, n; 10 11 int main(void) 12 { 13 #ifdef LOCAL 14 freopen("1024in.txt", "r", stdin); 15 #endif 16 17 while(scanf("%d%d", &m, &n) == 2) 18 { 19 int i, t; 20 memset(dp, 0, sizeof(dp)); 21 for(i = 1; i <= n; ++i) 22 scanf("%d", &a[i]); 23 for(i = 1, t = 1; i <= m; ++i, t = 1 - t) 24 { 25 dp[t][i] = dp[1-t][i-1] + a[i]; 26 dp[1-t][i] = max(dp[1-t][i], dp[1-t][i-1]); 27 for(int j = i + 1; j <= n - m + i; ++j) 28 { 29 dp[t][j] = max(dp[t][j-1], dp[1-t][j-1]) + a[j]; 30 dp[1-t][j] = max(dp[1-t][j], dp[1-t][j-1]); //此次更新以后dp[1-t][j]存放的是前j个数分成i-1段的最大值，并不要求a[j]在其中 31 } 32 } 33 int ans = -INF; 34 for(i = m; i <= n; ++i) 35 ans = max(ans, dp[m&1][i]); 36 printf("%d ", ans); 37 } 38 return 0; 39 }