Description

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

Input

第1行：1個整數N

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

Output

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

Sample Input

5
1
3
1
7
2

Sample Output

9

HINT

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

Source

Silver

?

好神的$dp$。 真的好難想。。

設$f[i][j]$表示還剩$i$個硬幣上一個人取了$j$個的最大收益

設$sum[i]$表示硬幣價值前綴和

那么我們有狀態轉移方程$f[i][j]=max(f[i][j],sum[i]-f[i-k][k])(1<=k<=min(i,2*j))$

這樣我們得到一個$O(n^3)$的算法，到這應該都還能理解

然而并不能跑過去，我們可以發（參）現（考）一個很吊的優（題）化（解）

我們考慮到$f[i][j]$和$f[i][j-1]$絕大多數狀態相同，我們只用再多考慮多出來的兩組即可

代碼：

1 #include<iostream> 2 #include<cstdio> 3 #define M 2010 4 using namespace std; 5 int n; 6 int a[M],f[M][M]; 7 int main() 8 { 9 scanf("%d",&n); 10 for(int i=n;i>=1;i--) scanf("%d",&a[i]); 11 for(int i=1;i<=n;i++) a[i]+=a[i-1]; 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=n;j++) 14 { 15 f[i][j]=f[i][j-1]; 16 int k=j*2; 17 if(i>=k) f[i][j]=max(f[i][j],a[i]-f[i-k][k]); 18 k=j*2-1; 19 if(i>=k) f[i][j]=max(f[i][j],a[i]-f[i-k][k]); 20 } 21 printf("%d",f[n][1]); 22 return 0; 23 }

?

轉載于:https://www.cnblogs.com/Slrslr/p/9576989.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[BZOJ2017][Usaco2009 Nov]硬币游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

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