題目描述

農夫約翰的奶牛喜歡玩硬幣游戲，因此他發明了一種稱為“Xoinc”的兩人硬幣游戲。 初始時，一個有N(5 <= N <= 2,000)枚硬幣的堆棧放在地上，從堆頂數起的第I枚硬幣的幣值為C_i (1 <= C_i <= 100,000)。 開始玩游戲時，第一個玩家可以從堆頂拿走一枚或兩枚硬幣。如果第一個玩家只拿走堆頂的一枚硬幣，那么第二個玩家可以拿走隨后的一枚或兩枚硬幣。如果第一個玩家拿走兩枚硬幣，則第二個玩家可以拿走1，2，3，或4枚硬幣。在每一輪中，當前的玩家至少拿走一枚硬幣，至多拿走對手上一次所拿硬幣數量的兩倍。當沒有硬幣可拿時，游戲結束。 兩個玩家都希望拿到最多錢數的硬幣。請問，當游戲結束時，第一個玩家最多能拿多少錢呢？

輸入

第1行：1個整數N

第2..N+1行：第i+1行包含1個整數C_i

輸出

第1行：1個整數表示第1個玩家能拿走的最大錢數。

樣例輸入

5
1
3
1
7
2

樣例輸出

9

提示

樣例說明：第1個玩家先取走第1枚，第2個玩家取第2枚；第1個取走第3，4兩枚，第2個玩家取走最后1枚。

?

不要看到博弈論就心里打怵，其實只是用到一些簡單的博弈思想qwq。這道題主要還是dp，那么dp狀態怎么描述呢？首先不能確定最后取硬幣的是先手的人還是后手的人，所以可以考慮把狀態倒著推，最終答案用先手的人第一次取的狀態表示。那么就可以把狀態描述成f[i][j]表示上一個人取了j個，還剩下i個，當前人在后續步驟中(包括當前這次取的)能獲得的最大值，s[i]表示最后i個的價值和(就是后綴和)。假設當前人是第一個人，他取了k個(k<=2*j)，第二個人之后能獲得的最大值就是f[i-k][k]，那么想讓第一個人這次及之后能獲得最大值，就要讓f[i-k][k]盡量小，那么只要枚舉k，用s[i]-min{f[i-k][k]}就是第一個人的最大值。但這樣枚舉k一定會TLE，不過可以發現f[i][j]和f[i][j-1]之間只差了f[i-2*j][2*j]和f[i-2*j+1][2*j-1]兩個狀態，所以可以把f[i][j]先賦成f[i][j-1]再與這兩個狀態比較一下就行了，但比較前要先判斷i和這兩個數(2*j和2*j-1)之間大小關系。但最后答案是什么呢?我們并不知道先手的人第一次取了1個還是2個,那么可以假設前面有一個第0號硬幣被第二個人取走了,這樣最終結果就是f[n][1].雖然狀態是倒著推,但為了方便可以倒著讀入正著轉移.

最后附上代碼.

#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n; int a[2010]; int s[2010]; int f[2010][2010]; int main() {scanf("%d",&n);for(int i=n;i>=1;i--){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=f[i][j-1];if(2*j-1<=i){f[i][j]=max(f[i][j],s[i]-f[i-2*j+1][2*j-1]);}if(2*j<=i){f[i][j]=max(f[i][j],s[i]-f[i-2*j][2*j]);}}}printf("%d",f[n][1]); }

　　

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9197069.html

總結

以上是生活随笔為你收集整理的BZOJ2017[USACO 2009 Nov Silver 1.A Coin Game]——DP+博弈论的全部內容，希望文章能夠幫你解決所遇到的問題。

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