题目大意:

Max Sum Plus Plus
给你m个数，在其中选取n组
使得每组的数连续，且互相不能相交,
求出最大的各组数的和

思路:

采取二维dp的方法
d p [ i ] [ j ] 中，i 为组数，j为以a [ j ] 结尾
状态转移方程为
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + a [ j ] , d p [ i − 1 ] [ k ] + a [ j ] ) ( 0 < k < j )
因为复杂度为O ( n² )，所以我们可以采取将二维dp变成一维dp，将其中的d p [ i − 1 ] [ k ] 用一个单独的一维数组表示

AC Code:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define INF 1<<30
const int N=1e6 +9;
int n, m;
int dp[N], f[N], a[N];
int main(){
	while(scanf("%d%d", &n, &m)!=EOF){
		memset(dp, 0, sizeof(dp));
		memset(f, 0, sizeof(f));
		for(int i=1; i<=m; i++)	scanf("%d", &a[i]);
		int mx=-INF;
		//
		for(int i=1; i<=n; i++){
			mx=-INF;
			for(int j=i; j<=m; j++){
				dp[j]=max(dp[j-1], f[j-1])+a[j];
				f[j-1]=mx;
				mx=max(dp[j], mx);
			}
		}
		printf("%d\n", mx);
	}
	return 0;
}