摘要：
1#include＜stdio.h＞2#include＜string。h˃ 3#include4usingspacestd；5约束N=1001000；6约束长度INF=0x3f3f3f3f3f3f3f3f；7longlongdp[2][N]，最大值；8英寸[N]；9intmain（）｛10intm，n，t；11while｛12t＝1；///用于滚动数组13 14 dp[0][i]=-INF；15 16扫描；17for｛///t=1-t表示在循环中滚动18dp[t][i]=dp[1-t][i-1]+a[i]；///对角线值实际上是前n项的总和！！19maxn＝dp[1-t][i-1]；//不要忘记20 for｛21maxn＝max；//maxn更新记录max22dp[t][j]=max+a[j]；///状态转换步骤23｝24｝25t=1-t///最后，当i˃m时，++i，t=1-t的影响将变为26maxn=-INF；27/**28注意，在a[j]的情况下，dp[i][j]是前j个数的最大和；29也就是说，dp[m%2][n不一定是最优解，因为在不添加a[n]的情况下，它可能更大；30**/31,32maxn=最大值；33printf；34}35返回0；36｝错误代码
题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1024
(http://www.fjutacm.com/Problem.jsp?pid=1375)
题意：长度为n的序列里，m段不相关区间的最大和
思路：我们先要确定一个东西，就是状态，这里我用dp[i][j]表示前j个数在取a[j]情况下分i段的最大和；
那么我们为了找规律，可以先来一发Excel，就以样例为例子：
然后我们可以发现其实红圈里的8是状态dp[2][6]（i=2， j=6），那么我们可以想想这个位置怎么推导，很明显，他可以选择和分i-1块的最大值相加，得到的i块可能是最大，或者他也可以直接和同样分i块的j-1的位置相加，这样就相当于不断开，得到最大。那么也就是他只有两种选择，第一个是dp[i][j-1]，第二个是max(dp[i-1][i-1]~dp[i-1][j-1])，也就是dp[i][i~n]只和dp[i-1][i-1~n]这一行的状态有关，和别的无关。那么我们就可以用滚动数组保存；但是如果你找max(dp[i-1][i-1]~dp[i-1][j-1])的时候用的是for查找的话，那就凉凉了，因为那样复杂度就是O(n^3)，也就是我们要用一个maxn来记住之前的最大值，然后每次更新记录；具体看代码。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 const int N= 1001000; 6 const long long INF=0x3f3f3f3f3f3f3f3f; 7 long long dp[2][N], maxn; 8 int a[N]; 9 int main( ){ 10 int m, n, t; 11 while(~scanf("%d%d", &m, &n)){ 12 t=1;///用来滚动数组 13 for(int i=1; i<=n; ++i) 14 dp[0][i]=-INF; 15 for(int i=1; i<=n; ++i) 16 scanf("%d", &a[i]); 17 for(int i=1; i<=m; ++i, t=1-t){///t=1-t就是在循环滚动 18 dp[t][i]=dp[1-t][i-1]+a[i];///对角线的值其实就是前n项和啦！！ 19 maxn=dp[1-t][i-1];///别把这个忘了 20 for(int j=i+1; j<=n; ++j){ 21 maxn=max(maxn, dp[1-t][j-1]);///maxn更新记录max(dp[i-1][i-1]~dp[i-1][j-1]) 22 dp[t][j]=max(dp[t][j-1], maxn)+a[j];///状态的转移步骤 23 } 24 } 25 t=1-t;///最后i>m时的那一个++i, t=1-t的影响要转过来 26 maxn=-INF; 27 /** 28 注意，dp[i][j]是表示前j个数在取a[j]情况下分i段的最大和； 29 也就是dp[m%2][n不一定是最优解，因为可能不加a[n]还更大； 30 **/ 31 for(int i=m; i<=n; ++i) 32 maxn=max(maxn, dp[t][i]); 33 printf("%I64d ", maxn); 34 } 35 return 0; 36 }