HDU 5623KK's Number DP

题意: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 ;
}
上一篇:Eclipse开发快捷键技巧


下一篇:【转载】如何用IntelliJ IDEA 14 创建Web项目