link：http://acm.hdu.edu.cn/showproblem.php?pid=4701

DP真美 ！ ?(亝 ? 亝)

?

dp[pos][a][b][0/1]：第pos件商品即將被購買，Alice有a元， Bob有b元，輪到誰行動(0:Alice 1:Bob)。

打訓練賽時，設計出來了這樣一個狀態。然后發現了pos和a能表示出b呀！于是，省掉了一維，然后就不會

了。之后嘗試著貪心，效果不佳。

?

先來個小小的降維~

dp[pos][x]：第pos件商品即將被購買，面臨著這個局面的人有x元。能否獲勝呢？

看來，求索未得啊！空間復雜度還是爆炸。然而dp[pos][x]僅僅表達0/1的話是不是有點浪費呢？這樣來試試

dp[pos]：第pos件商品即將被購買，面臨此局面的人至少需要多少元才可獲勝？

nice！這個狀態設計的挺令人滿意的！

然后就可施展我們的博弈思想。若想勝，則需一個GG的后繼.

即將行動的人的錢：dp[pos]

對手的錢：a+b - dp[pos] - sum[pos-1]?

?

為了找到這么一個后繼，則存在nxt>pos滿足這樣兩個條件：

dp[pos] >= ?a + b - sum[pos-1] - dp[nxt] + 1 ?

dp[pos] >= ?sum[nxt-1] - sum[pos-1]

令a + b - sum[pos-1] - dp[nxt] + 1 = Ans1,?sum[nxt-1] - sum[pos-1] = Ans2

dp[pos] = min{ max(Ans1, Ans2) }

然后從后往前，一遍計算dp[i]，一遍維護max(Ans1, Ans2)最小值。O(n)

#include <iostream> using namespace std; typedef long long LL; const int NICO = 1000002; LL n, a, b, x; LL sum[NICO]; int main() {while(~scanf("%lld %lld %lld", &n, &a, &b)){for(int i=1;i<=n;i++){scanf("%lld", &x);sum[i] = sum[i-1] + x;} LL pre = sum[n], now = 0;for(int i=n;i>=1;i--){now = pre - sum[i-1];//cout << i << " : " << now << endl;pre = min(pre, max(sum[i-1], a+b-now+1));}printf("%s\n", now>a?"BOB":"ALICE");} }

　　

?

轉載于:https://www.cnblogs.com/RUSH-D-CAT/p/6854704.html

總結

以上是生活随笔為你收集整理的HDU 4701 Game的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。