★HDU 1024 Max Sum Plus Plus 【DP】

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1024


★这题好难的。。。我真是看了好几个小时，搜了好多题解，现在还是似懂非懂~mark一下 留个坑
然后推荐你们去看看这篇博客：https://blog.****.net/qq_34374664/article/details/52266684

翻译：

求一个给定数组的 m个不相交的区间的和的最大值
例二：分为2个区间，4和 3 -2 3 ，加起来和为8

思路：

最原始的DP方程 dp[ i ][ j ]=Max( dp[ i ][ j-1 ]+a[ j ] , max( dp[ i-1 ][ k ] ) + a[ j ] )
其中0<k<j ,dp[ i ][ j ]指的是前j个数分为i段的最大和
dp[ i ][ j-1 ]+a[ j ] 指的是a[ j ]单独作为一段
max( dp[ i-1 ][ k ] ) + a[ j ] 指的是 a[ j ]与前面一个区间成一段
但是题目数据比较大，最后不是爆内存就是TLE，行不通~需要优化
然后我们容易发现 max( dp[ i-1 ][ k ] )就是 上一组 dp[ i-2 ][ * ] 的最大值，用一个一维数组 f[ maxn ] 保存下来就好,a[ maxn ] 保存输入的数据~
其他的要点在代码中注释了~

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e6+5;
int f[maxn],a[maxn],dp[maxn];
int main()
{
    int n,m;
    while(cin>>m>>n){
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            f[i]=dp[i]=0;        //初值全为0
        }
        int ans;
        f[0]=dp[0]=0;
        for(int i=1;i<=m;i++){     //分为i组
            ans=-1e9;
            for(int j=i;j<=n;j++){         //j个数分为i组
                dp[j]=max(dp[j-1],f[j-1])+a[j];   //转移方程
                f[j-1]=ans;                     //分成i-1组j-1个的最大值
                ans=max(ans,dp[j]);             //也是为了更新f[j-1]，同时得到最优解
            }
        }
        cout<<ans<<endl;
    }
}