HDU 5623 KK's Number
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5623
题目翻译
http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=669&pid=1004
题解
( F \left [ x \right] ) 表示当前先手取到数字( x )为止所能达到的最大数字差。
明显，( F \left [ i \right ] = max \left { i – F \left[ j \right ] \right } , \left ( i > j \right ) )
但是这样会超时。
我们可以从小到大DP，这样就是( O \left( n \right) )的了。
( F \left [ i \right] = i – preMax )
( preMax = max \left ( preMax , F \left [ i \right ] \right ) )
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define LL long long using namespace std; const int Maxn=5e4; int num[Maxn+5]; int n; int stk[Maxn+5]; int top; inline bool cmp(int a,int b){ return a<b; } LL F[Maxn+5]; LL preMax; inline void solve(int T){ scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&num[i]); top=0; sort(num+1,num+n+1,cmp); for (int i=1;i<=n;i++) if (top==0 || stk[top]!=num[i]) stk[++top]=num[i]; F[0]=preMax=0; for (int i=1;i<=n;i++){ F[i]=num[i]-preMax; preMax=max(preMax,F[i]); } printf("%I64d\n",preMax); } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for (int i=1;i<=T;i++) solve(i); return 0; } |
原文链接：HDU 5623 KK's Number
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!