题意：n个元素的数组，求分成m个不相交段的方法，使这m段之和最大，输出最大和

思路：dp，状态dp[i][j]表示前j个物品分成i段的最大和，

    状态转移方程：dp[i][j]=max(dp[i][j-1]+arr[j],max(dp[1][j-1]~dp[i-1][j-1] )+arr[j])

    决策：第j个物品①放入现有的i组合求和 ②成为第i组，与前面的i-1组求和

    数据量大，用一维数组压缩一下空间

代码：

#include
     
      #include
      
       #include
       
        using namespace std;#define maxn 1001001#define inf 0x3f3f3f3fint dp[maxn];int maxpre[maxn];int arr[maxn];int m, n;int main() {	while (scanf("%d %d", &m, &n) != EOF) {		for (int i = 1; i <= n; i++) {			scanf("%d", &arr[i]);			dp[i] = 0;			//maxpre[i] = -2;			maxpre[i] = 0;		}		int mmax = -inf;		maxpre[0] = 0;		dp[0] = 0;		for (int i = 1; i <= m; i++) {			mmax = -inf;			for (int j = i; j <= n; j++) {				dp[j] = max(dp[j - 1] + arr[j], maxpre[j - 1] + arr[j]);				//cout << dp[j] << endl;				maxpre[j - 1] = mmax;				mmax = max(mmax, dp[j]);			}		}		printf("%d\n", mmax);	}}
       
      
     

一开始把maxpre全设为无穷小，结果第二组样例小了1。。。

把dp值全打印出来，发现在状态转移的时候，dp[2]跟-1结合了，因为-inf太小。。。orz