传送门
短代码神奇dp。
自己yy的思路居然1A了好高兴啊！
不难想到每个人选择的时候一定是取连续的最大的那一段数，自然需要先排序。
然后可以用dp[i]表示当前最大数是a[i]的时候先手可以获得的最优值。
不难想到dp[i]跟dp[1]~dp[i-1]都有关系，其实就是dp[i]=max(a[j]−dp[j−1])" role="presentation" style="position: relative;">dp[i]=max(a[j]−dp[j−1])dp[i]=max(a[j]−dp[j−1])，然后可以发现这个东西当j<i" role="presentation" style="position: relative;">j<ij<i时都在推dp[i-1]的时候求过一遍了，于是dp[i]=max(dp[i−1],a[i]−dp[i−1])" role="presentation" style="position: relative;">dp[i]=max(dp[i−1],a[i]−dp[i−1])dp[i]=max(dp[i−1],a[i]−dp[i−1])
于是又多了一道短代码题。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
ll a[N],dp[N];
int n;
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+n+1);
dp[0]=0,dp[1]=a[1];
for(int i=2;i<=n;++i){
dp[i]=dp[i-1];
dp[i]=max(dp[i],a[i]-dp[i-1]);
}
cout<<dp[n];
return 0;
}