首页 > 代码库 > BZOJ 2091: [Poi2010]The Minima Game
BZOJ 2091: [Poi2010]The Minima Game
Description
每次可以任取数字,使用最优策略让差最大.
Sol
DP.
一开始我写了个单调队列贪心,然后狂WA不止...
正着做有后效性,因为前面的决策无法保证在后面是最优秀的,但如果倒这做就没有后效性了..感觉倒着做这种想法总是容易忽略,它对前面的影响应该多考虑一下.
然后DP就可以了...比较简单的DP..
Code
/************************************************************** Problem: 2091 User: BeiYu Language: C++ Result: Accepted Time:1248 ms Memory:16916 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 1e6+50; LL n,mx;LL a[N],f[N]; inline LL in(LL x=0,char ch=getchar()) { while(ch>‘9‘ || ch<‘0‘) ch=getchar(); while(ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();return x; }int main() { n=in(); for(int i=1;i<=n;i++) a[i]=in(); sort(a+1,a+n+1);mx=a[1]; for(int i=1;i<=n;i++) f[i]=mx,mx=max(mx,a[i+1]-f[i]); cout<<f[n]<<endl; return 0;}
BZOJ 2091: [Poi2010]The Minima Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。