E - Max Sum Plus Plus Plus HDU - 1244 （线性区间DP）

题目大意：值得注意的一点是题目要求的是这些子段之间的最大整数和。注意和Max Sum Plus Plus这个题目的区别。

题解：

线性区间DP，对每一段考虑取或者不取。定义状态dp[i][j]指的是前i个数分为j段。

如果第j段不选的话dp[i][j]=dp[i-1][j]，直接就是上一个状态的值。

如果选得话，dp[i][j]=dp[i-part[j]][j-1]+sum[i]-sum[i-part[j]]。前一共有i个数，第j段要占用i-part[j]个数，所以前j-1段要占用

i-part[j]个数。然后取最好的状态就行了。复杂度O(n*m)

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N=+;

ll dp[N][N];

ll arr[N];

ll part[N];

ll sum[N];

int main(){

    ll n;

    while(cin>>n,n){

        ll m;

        cin>>m;

        memset(dp,,sizeof dp);

        memset(sum,,sizeof sum);

        for(ll i=;i<=m;i++) cin>>part[i];

        for(ll i=;i<=n;i++) cin>>arr[i];

        for(ll i=;i<=n;i++) sum[i]=sum[i-]+arr[i];

        for(ll i=;i<=n;i++)

            for(ll j=;j<=m;j++){

                if(part[j]>i) dp[i][j]=dp[i-][j];

                else dp[i][j]=max(dp[i-][j],

                dp[i-part[j]][j-]+sum[i]-sum[i-part[j]]);

            }

        cout<<dp[n][m]<<endl;

    }

    return ;

}

巴特西

E - Max Sum Plus Plus Plus HDU - 1244 （线性区间DP）

最新文章

热门文章