P3507 GRA-The Minima Game

枫林晚

2018-04-26 17:40:49

Solution

### 题目大意: 给出N个正整数,AB两个人轮流取数,A先取。每次可以取任意多个数,直到N个数都被取走。每次获得的得分为取的数中的最小值,A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下,最终A的得分减去B的得分为多少。 ### 分析: 我们身临其境地考虑一下,先手肯定是要从大到小取数,并且一定取的是连续的一段。 证明: 从大到小取数显然,若不是连续取数,则留下的数更多,大的数更多,会给对方更多的机会。所以必然是连续取数。 所以我们倒着来考虑一下,将所有的数从小到大排列之后,f[i]表示两人取完前i个数,先手减去后手的最大值,(这里先手后手是相对的,因为我们是倒序的,和实际取法是完全相反的,它实际上是处理出了1~i个数的情况下的最优解,A先从i开始往左边取,所以说考虑先手减后手最大值) 这样的话,每到一个i,我们可以枚举一下A先手第一步从i取到哪里。而剩下的一段必然是换B当先手来操控。 f[i]=max(a[j]-f[j-1])(1<=j<=i) j的意义是:A先手从i取到j,由于单调递减,所以他的得分就是a[j],但是剩下的肯定由B来操控出f[j-1],即1~j-1数的先手最大值,这样,A实际做出的超越,就是a[j]-f[j-1],保证先手使得差距最大,所以从所有的a[j]-f[j-1]中取一个max值。 这个max可以前缀最大值优化处理。 更简单的是:因为f[i-1]就是由这个max值转移过来的,所以f[i]=max(f[i-1],a[i]-f[i-1]) 代码: ```cpp #include<bits/stdc++.h> using namespace std; const int N=1000000+10; int n,a[N]; long long f[N]; 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++) f[i]=max(f[i-1],a[i]-f[i-1]); printf("%lld",f[n]); return 0; } ```