题意：bc round 71 div 1 1003(有中文题面)
分析：
显然，每个人的策略就是都会拿剩下的数中最大的某几个数
假如我们用dp[i]表示当剩下i个数的时候先手得分-后手得分的最优值
那么得到dp[i]=max(a[j]-dp[j-1])(1<j≤i)
但是这样做，是要超时的
我们不妨简单转换一下 _max=max(_max,a[i]-dp[i-1]),dp[i]=_max;
这样在因为我们只需要a[i]-dp[i-1],所以随着循环，更新最大值就好了
时间复杂度O(N)
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; const int maxn=5e4+5; int a[maxn],dp[maxn]; int main() { int T,n,mx; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",&a[i]); sort(a+1,a+1+n); dp[1]=mx=a[1]; for(int i=2;i<=n;++i){ mx=max(mx,a[i]-dp[i-1]); dp[i]=mx; } printf("%d\n",dp[n]); } return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5184740.html
