题意: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+;
int a[maxn],dp[maxn];
int main() {
int T,n,mx;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=;i<=n;++i)scanf("%d",&a[i]);
sort(a+,a++n);
dp[]=mx=a[];
for(int i=;i<=n;++i){
mx=max(mx,a[i]-dp[i-]);
dp[i]=mx;
}
printf("%d\n",dp[n]);
}
return ;
}