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;
}