BZOJ 2091: [Poi2010]The Minima Game 博弈dp

十分有趣的问题.

我们发现如果拿的话肯定要先拿一些大的.

所以我们可以先将所有数从小到大排序，令 $f[i]$ 表示拿完前 $i$ 小先手-后手的最大值.

则有转移：$f[i]=max(f[i-1],a[i]-f[i-1])$

反复阅读：每次拿一些数字的贡献是这些数字中最小的值.

反复阅读上一句话，然后再看一看式子就容易懂了.

code:

#include <bits/stdc++.h>

#define N 1000006

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

ll f[N],a[N];

int main()

{

    // setIO("input");

    int i,j,n;

    scanf("%d",&n);

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

    sort(a+1,a+1+n);

    for(i=1;i<=n;++i)

    {

        f[i]=max(f[i-1],a[i]-f[i-1]);

    }

    printf("%lld\n",f[n]);

    return 0;

}

巴特西

BZOJ 2091: [Poi2010]The Minima Game 博弈dp

最新文章

热门文章