【codevs】3196 黄金宝藏

【算法】区间DP+博弈论

【题解】其实它都不是博弈题……

很自然的可以设f[i][j]表示i~j先手可取得的最大价值。

容易得到转移式：f[i][j]=max(a[i]+sum[i+1~j]-f[i+1][j]，a[j]+sum[i~j-1]-f[i][j-1])。

化简得到f[i][j]=sum[i~j]-min(f[i+1][j]，f[i][j-1])。

然后预处理前缀和，按区间从小到大做即可。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int a[maxn],f[maxn][maxn],sum[maxn],n;

int main()

{

    scanf("%d",&n);

    sum[]=;

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

    for(int p=;p<n;p++)

    for(int i=;i<=n-p;i++)

    f[i][i+p]=sum[i+p]-sum[i-]-min(f[i+][i+p],f[i][i+p-]);

    printf("%d %d",f[][n],sum[n]-f[][n]);

    return ;

}

因为按区间大小递推所以还可以缩一维空间。

极大极小搜索是什么，可以吃吗？

巴特西

【codevs】3196 黄金宝藏

最新文章

热门文章