HDU 1024 Max Sum Plus Plus（求m个不相交连续子序列最大和/01背包）

题目链接：
HDU 1024 Max Sum Plus Plus
题意：
n个数，求m个不相交连续子序列的最大和。n<=1e6，单个数[-32768,32767]，m>0.
分析：
dp[i][j][1]表示在求前i个数的j个不相交的最大子序列和时不要第i个数
dp[i][j][0]表示要第i个数。
*初始化：*
dp为-INF，但是dp[0][0][0]=dp[0][0][1]=0；
*状态转移方程：*
如果第i个数要：
考虑第i-1个数要不要，如果要的话，将第i个数合并进第i-1个数所属于的第j个子序列(dp[i-1][j][0])或者第i个数独自成为第j个子序列(dp[i-1][j-1][0]),
如果不要，那么第i个数独自成为第j个子序列(dp[i-1][j-1][1])
即：dp[i][j][0]=max(max(dp[i-1][j][0],dp[i-1][j-1][0]),dp[i-1][j-1][1])+data[i];
如果第i个数不要：dp[i][j][1]=max(dp[i-1][j][0],dp[i-1][j][1]);
但是这样做有一个问题–数组太大，但是可以用滚动数组的方法解决。
注意：
这道题没指定m的范围，但是亲测1000多一点！因为下面代码中我一开始定义MAX_M是1000，结果WA了好久，改成1010居然AC了！！！！还有数据可能很极端，所以初始化的-INF要尽可能小，dp数组用long long。

//483MS 2126K
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_M=1010;
const int MAX_N=1000010;

int n,m;
long long data[MAX_N],dp[MAX_M][2];

int main()
{
//freopen("1024in.txt","r",stdin);
    dp[0][0]=dp[0][1]=0;
while(~scanf("%d%d",&m,&n)){
for(int i=1;i<=n;i++){
scanf("%lld",&data[i]);
        }
for(int i=1;i<=m;i++){
            dp[i][0]=dp[i][1]=LONG_LONG_MIN/2;
        }
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
                dp[j][1]=max(dp[j][0],dp[j][1]);
                dp[j][0]=max(max(dp[j][0],dp[j-1][1]),dp[j-1][0])+data[i];
            }
        }
printf("%lld\n",max(dp[m][1],dp[m][0]));
    }

return 0;
}