思路：
dp[i][j] 表示前j个数在把第j个数放在最后一组的前提下，分成i组的最大和
那么 状态转移 dp[i][j] = max(dp[i][j-1]+save[j],max(dp[0][j-1] ~ dp[i-1][j-1])+save[j]);//表示第j个放在第i组中，和第j个独立成组。
然后滚动数组在滚动数组中不断更新max 不能每次用循环求出。
#include#include #include #include #define inf 0x7fffffff using namespace std; int dp[1000010]; int save[1000010]; int M[1000010]; int n,m,Max; int main() { while(scanf("%d%d",&m,&n)!=EOF) { for(int i=1;i<=n;i++)scanf("%d",&save[i]); memset(dp,0,sizeof dp); memset(M,0,sizeof M); for(int i=1;i<=m;i++) { Max=-inf; for(int j=i;j<=n;j++) { dp[j]=max(dp[j-1]+save[j],M[j-1]+save[j]); M[j-1]=Max; Max=max(dp[j],Max); } } printf("%d\n",Max); } return 0; }