题目大意：
给出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])
代码：
#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; }