LightOJ 1031 Easy Game (区间DP)

题目大意：

给定一段序列，两人轮流取数，每人每次只能从序列的两端的任意一段取数，取的数字位置必须连续，个数不限，问你这两人取数的最大差值是多少。

解题分析：

每人取数时面对的局面是一段连续的子序列，我们不妨假设$dp[l][r]$为对于区间$[l,r]$，两人取数的最大差值。因为可能要进行连续区间的转移，所以我们枚举区间之后，还要枚举断点。先预处理出前缀和，对于区间[l,r],dp[l][r]=max(dp[l][r],max((sum[k]-sum[l-1]-dp[k+1][r])，(sum[r]-sum[k]-dp[l][k]))) ,分别表示先手取区间[l,k] 或 [k+1,r] 时，在区间[l,r]中，两人取数差值的最大值。

#include <bits/stdc++.h>

using namespace std;

const int N = ;

int n,dp[N][N],arr[N],sum[N];

int main(){

    int T,ncase=;scanf("%d",&T);

    while(T--){

        sum[]=;scanf("%d",&n);

        memset(dp,-0x3f,sizeof(dp));

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

            scanf("%d",&arr[i]);

            sum[i]=sum[i-]+arr[i];

            dp[i][i]=arr[i];

        }

        for(int len=;len<=n;len++){

            for(int l=;l+len-<=n;l++){

                int r=l+len-;

                dp[l][r]=sum[r]-sum[l-]; //取整个区间的情况，这里不能漏

                for(int k=l;k<r;k++){     //因为可以取连续的区间，需要进行区间的转移，所以这里要枚举断点

                    dp[l][r]=max(dp[l][r],max((sum[k]-sum[l-]-dp[k+][r]),(sum[r]-sum[k]-dp[l][k])));

                }//(sum[k]-sum[l-1]-dp[k+1][r])表示：[l,r]中先手取[l,k]时的差值

            }

        }

        printf("Case %d: %d\n",++ncase,dp[][n]);

    }

}

巴特西

LightOJ 1031 Easy Game (区间DP)

最新文章

热门文章