【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=510;
int a[maxn],f[maxn][maxn],sum[maxn],n;
int main()
{
    scanf("%d",&n);
    sum[0]=0;
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}
    for(int p=0;p<n;p++)
    for(int i=1;i<=n-p;i++)
    f[i][i+p]=sum[i+p]-sum[i-1]-min(f[i+1][i+p],f[i][i+p-1]);
    printf("%d %d",f[1][n],sum[n]-f[1][n]);
    return 0;
}

View Code

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

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