bzoj 2091: [Poi2010]The Minima Game【博弈论+贪心+dp】

不知道算不算博弈

很妙的贪心，一直在想SG函数结果...

首先从大到小排个序，然后考虑当前的人要怎么选：如果不选最后一段，那么另一人会选，这样不利于当前的人，所以每个人一定会选最后一段

设f[i]为要选i了，先手的最大差，显然是max(a[i]-f[i-1],f[i-1])，就是先手只选了最后一个和先手选了i,i-1....

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[1000005],ans;

int main()

{

    scanf("%d",&n);

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

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

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

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

		ans=max(a[i]-ans,ans);

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

	return 0;

}

巴特西

bzoj 2091: [Poi2010]The Minima Game【博弈论+贪心+dp】

最新文章

热门文章