hdu 1024（dp）

题意：从n个数中选出m段不相交的连续子段，求这个和最大。

分析：经典dp，dp[i][j][0]表示不取第i个数且前i个数分成j段达到的最优值，dp[i][j][1]表示取了第i个数且前i个数分成j段达到的最优值。

那么有：

dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]).

dp[i][j][1]=max(dp[i-1][j-1][0]+a[i],max(dp[i-1][j-1][1],dp[i][j][1])+a[i])).

红色部分略坑，仔细体会一下，因为连续的一段可能拆成多一段刚好符合m段到达最好，不一定得选一段连续的子系列只当成一段最好，可能分成多段更优。

由于n过大，使用滚动数组优化空间。

#include <algorithm>

#include <cstdio>

#include <cstring>

#define N 1000010

#define inf 0x3f3f3f3f

using namespace std;

int dp[][N][],a[N];

int n,m;

int main()

{

    while(scanf("%d%d",&m,&n)>)

    {

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        for (int i = ; i <= m; i++) {

            dp[][i][] = dp[][i][] = dp[][i][] = dp[][i][] = -inf;

        }

        dp[][][]=dp[][][]=;

        for(int i=,t=;i<=n;i++,t=!t)

        {

            for(int j=;j<=i&&j<=m;j++)

            {

                dp[t][j][]=max(dp[!t][j][],dp[!t][j][]);

                if(j)dp[t][j][]=max(dp[!t][j-][]+a[i],max(dp[!t][j][],dp[!t][j-][])+a[i]);

            }

        }

        printf("%d\n",max(dp[n&][m][],dp[n&][m][]));

    }

}

巴特西

hdu 1024（dp）

最新文章

热门文章