2091: [Poi2010]The Minima Game DP

鏈接

https://www.lydsy.com/JudgeOnline/problem.php?id=2091

思路

這類問題好迷呀。
我們先從小到大sort
先手一定是個后綴。
因為你不能留下大數(shù)讓對手選呀。
然后后手就在你選擇的i前面選([1,i-1])后手及其之后的操作。
f[i]表示前i個里面先手的最大值
f[i]=min(f[i-1],a[i]-f[i-1])
要不這個i點沒有貢獻(xiàn),先手是f[i-1],要不就是選這個點，后手是f[i-1]

代碼

#include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e6+7; int read() {int x=0,f=1;char s=getchar();for(;s>'9'||s<'0';s=getchar()) if(s=='0') f=-1;for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';return x*f; } int n,a[N]; ll f[N],ans; int main() {n=read();for(int i=1;i<=n;++i) a[i]=read();sort(a+1,a+1+n);for(int i=1;i<=n;++i) f[i]=max(f[i-1],a[i]-f[i-1]);cout<<f[n];return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/dsrdsr/p/10623608.html

總結(jié)

以上是生活随笔為你收集整理的bzoj2091: [Poi2010]The Minima Game DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。