HDU 1024 Max Sum Plus Plus(dp)

Max Sum Plus Plus
选m段不相交的子数组，求最大和。
设 $dp[i][j]$ 代表以 $s[j]$ 结尾,前 $j$ 个数分成 $i$ 段的最大值。
所以 $s[j]$ 必须选，要么和 $dp[i][j-1]$ 的 $s[j-1]$ 合在一起，要么和 $dp[i-1][j-1]$
的 $s[j-1]$ 形成一段，或者独自成一段。
所以转移方程： $dp[i][j]=max(dp[i][j-1],dp[i-1][j-1])+s[j]$ 。 $ans=max(ans,dp[m][j])$ 。
状态只跟上一层有关，所以可以优化下空间。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int m,n;
int s[N];
ll dp[2][N];
int main(){
    while(sc("%d%d",&m,&n)>0){
        me(dp,0);
        ll ans=0;
        for(int i=1;i<=n;i++)sc("%d",&s[i]);
        for(int i=1;i<=m;i++){
            ans=-1e9;
            for(int j=i;j<=n;j++){
                dp[1][j]=max(dp[1][j-1],dp[0][j-1])+s[j];
                dp[0][j-1]=ans;
                ans=max(ans,dp[1][j]);
            }
        }
        pr("%lld\n",ans);
    }
    return 0;
}
/*
    for(int i=1;i<=m;i++){
        for(int j=i;j<=n;j++){
            dp[i][j]=max(dp[i][j-1],dp[i-1][j-1])+s[j];
        }
    } 
 */