Max Sum Plus Plus
题意：题意理解了老半天，这里是说在给定数列中，取m组子数列，不能有重复，使得这些子序列的和最大；
就比如m=2时候，1 /2/-4/5/6.可以不用拿-4的意思；
思路：这道题的思路是动态规划，递推；
状态dp[i][j]
表示有前j个数，组成i组的和的最大值。
决策： 第j个数，要么包含在第i组里面，要么自己独立成组。
其中最后一组包含a[j]。(这很关键)
则状态转移方程为：（在二维图中，就是要么从左边取，要么取上一行的最大值，下式中，左边max是包含在第i组里，右边max是独立成组）
dp[i][j]=max{dp[i][j-1]+a[j],max{dp[i-1][t]}+a[j]} i-1=<t<j-1
此题n数据太大，二维数组开不下，而且三重循环，想到状态转移方程后还是困难重重。
想想，二维数组不行的话，肯定要压缩成一维数组：
因为dp[i-1][t]的值只在计算dp[i][j]的时候用到，那么没有必要保存所有的dp[i][j] for i=1 to m,这样我们可以用一维数组存储。
用pre[ j ]表示 j 之前一个状态 dp[i-1][ ]中1-j之间的最大字段和（不一定包含 a[j] ），然后推dp[ i ][ j ]状态时，dp[ i ][ j ]=max{pre[j-1]，dp[j-1]}+a[j];
红色的为了方便理解，其实不存在。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std; const int maxn = +;
const int inf = 0x3f3f3f;
int pre[maxn],dp[maxn],a[maxn];
int n,m;
int main(){
while(~scanf("%d%d",&m,&n))
{
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
dp[]=;
memset(pre,,sizeof(pre));
int mmax;
for(int i=;i<=m;i++)
{
mmax = -inf;
for(int j=i;j<=n;j++)//对于每个i，随着j的增大，maxx越滚越大，（贪心求连续和最大
{
dp[j] = max(dp[j-],pre[j-])+a[j];
pre[j-] = mmax;//把前一轮（j-1）的最大值赋给pre；
//注意这是第二句，因为pre只能在（i+1）轮起作用；
mmax = max(mmax,dp[j]);
}
}
printf("%d\n",mmax);//最后一轮的最大值就是答案。
}
return ;
}
//给了一组数据，不理解就把所有DP打出来，自己手动模拟一遍，这样好理解多了
/* 4 7
1 2 -4 5 6 -8 10
*/