原题链接：
题意：
给你一个长为 \(N\)的序列。你要将其分为 \(M\) 段不重叠的连续区间 ， 使得这些区间的总和最大。
思路：
我们先从状态来看。一般关于序列问题我们很容易想到 以第 \(j\) 个数结尾的状态。然后再结合这道题的 \(M\) 个不同区间，我们可以再设一个 区间个数为 \(i\) 的状态。即最后 \(dp [i] [j]\)表示以第\(j\)个数结尾，分为\(i\)个区间的状态 。
我们再来分析状态转移：我们知道 \(dp[i][j]\) 可以由 \(dp[i][j-1]+arr[j]\) 得来，即我们取第 \(j\)位且将其与前面一个区间连在一起算同一个（即区间个数没有变化的情况）
另一种就是区间个数\(+1\)的情况。我们可以由 \(dp[i-1][k]+arr[j]\) 得到。这里的\(k\)为比 \(i-1\)大，比\(j\)小的所有状态。（由于有\(i-1\)个区间所以结尾至少为\(i-1\),同时由于是从\(j\)之前的状态来的所以只能到\(j-1\)）
我们再看题中序列个数，在\(10^6\) 太大了，同时我们之前也得到了 \(dp[i][j]\space=\space max(dp[i][j-1]+arr[j],dp[i-1][k]+arr[j])\) 这个状态转移方程，发现只由两种状态的\(i,i-1\)递推。so，我们就用滚动数组。名字虽然高级实际上就是 由于每次递推只与两种相邻状态相关，所以不需要再记录之前的信息。然后关于\(dp[i-1][k]+arr[j]\),我们可以在递推过程中用一个MAX来记录这个范围类状态的最值。
code:
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6+5; const int inf = 0x3f3f3f3f; int dp[2][maxn]; int arr[maxn]; int main(){ int n,m; while(~scanf("%d %d",&n,&m)){ for(int i=1;i<=m;i++){ dp[0][i] = dp[1][i] = 0; scanf("%d",&arr[i]); } dp[1][0] = dp[0][0] = 0; int r = 1;//r表示当前状态 int Max; for(int i=1;i<=n;i++){ Max = -inf; for(int j=i;j<=m;j++){ dp[r][j] = max(dp[r][j-1],dp[r^1][j-1])+arr[j]; dp[r^1][j-1] = Max; Max = max(Max,dp[r][j]); } } printf("%d\n",Max); } }转载于:https://www.cnblogs.com/Tianwell/p/11407932.html
