bzoj 2017 [Usaco2009 Nov]硬币游戏动态规划

[Usaco2009 Nov]硬币游戏

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 431 Solved: 240
[Submit][Status][Discuss]

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

HINT

样例说明：第1个玩家先取走第1枚，第2个玩家取第2枚；第1个取走第3，4两枚，第2个玩家取走最后1枚。

Source

Silver

题解：

　　dp[i,j]:剩下i枚硬币,前一个人拿了j枚,自己最大的收益

　　ans=dp[n,1]

　　转移

　　　　dp[i,j]=max{sum[i]−dp[i−k,k]}     (1≤k≤min(2j,i))
　　　　dp[i,j]=sum[i]−max{dp[i−k,k]}     (1≤k≤min(2j,i))
　　　　dp[i,j−1]=sum[i]−max{dp[i−k,k]}     (1≤k≤min(2j−2,i))

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define N 2007

 #define inf 1000000007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 int c[N],sum[N],dp[N][N];

 int main()

 {

     n=read();

     for (int i=n;i;i--) c[i]=read();

     for (int i=;i<=n;i++) sum[i]=sum[i-]+c[i];

     for (int i=;i<=n;i++)

     {

         int mn=inf;

         for (int j=;j<=n;j++)

         {

             int t=min(j*,i);

             mn=min(mn,dp[i-t][t]);

             t=min(j*-,i);

             mn=min(mn,dp[i-t][t]);

             dp[i][j]=sum[i]-mn;

         }

     }

     printf("%d",dp[n][]);

 }

巴特西

bzoj 2017 [Usaco2009 Nov]硬币游戏动态规划

[Usaco2009 Nov]硬币游戏

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

巴特西

bzoj 2017 [Usaco2009 Nov]硬币游戏 动态规划

[Usaco2009 Nov]硬币游戏

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章

bzoj 2017 [Usaco2009 Nov]硬币游戏动态规划