[文章目录]
Description
给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下，最终A的得分减去B的得分为多少。
博弈DP
每次都是拿最大若干个数。
证明：如果有空余，那么第二个人一定选择只空余，解会更差。
那么设f[i]表示前i小的数进行游戏的答案，那么则有f[i]=max(f[i-1~1],a[i]-f[i-1])=max(f[i-1],a[i]-f[i-1])
排序后DP即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,a[1001000];
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF:*p1++;
}
inline void read(int &x)
{
char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
ll Max(ll x,ll y){return x>y ? x:y;}
int main()
{
read(n); for(register int i=1;i<=n;++i) read(a[i]);
sort(a+1,a+n+1); ll now=0;
for(int i=1;i<=n;++i)
now=Max(now,-now+a[i]);
printf("%lld",now);
return 0;
}