HihoCoder1338 A Game (区间DP)

<题目链接>

题目大意：

两个人轮流从一个序列中取数，他们都面临同样的二选一决策：是拿走最左边的数，还是拿走最右边的数？问先手最多能够得到的分数是多少。

解题分析：

一道比较经典的DP，因为每次只能从数组的两端取走一个数，所以每次面对的数组都只可能是一段连续的子数组。我们不妨假设$dp[l][r]$表示对于数组$A[i]~A[j]$，先手能够获得的最多得分。于是状态的转移就不难得出了。

枚举所有区间：

$l==r$的时候，肯定是$dp[l][r]=arr[l]$

而对于其他区间大于1的情况，$dp[l][r]=max(dp[l][r],((sum[r]-sum[l-1])-min(dp[l+1][r],dp[l][r-1])))$

官方题解 >>>

递推DP

#include <bits/stdc++.h>

using namespace std;

#define N int(1e3+5)

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

int main(){

    scanf("%d",&n);

    sum[]=;

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

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

    for(int i=n;i>=;i--){

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

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

            dp[i][j]=max(dp[i][j],(sum[j]-sum[i-])-min(dp[i+][j],dp[i][j-]));

        }

    }

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

}

记忆化搜索

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3+;

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

int DP(int l,int r){

    if(l>r)return ;

    if(dp[l][r]!=-)return dp[l][r];

    dp[l][r]=-1e9;

    if(l==r)dp[l][r]=arr[l];

    else dp[l][r]=max(dp[l][r],(sum[r]-sum[l-])-min(DP(l+,r),DP(l,r-)));

    return dp[l][r];

}

int main(){

    scanf("%d",&n);

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

        scanf("%d",&arr[i]),sum[i]=sum[i-]+arr[i];

    }

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

    printf("%d\n",DP(,n));

}

巴特西

HihoCoder1338 A Game (区间DP)

最新文章

热门文章