首页 > 代码库 > bzoj2017[Usaco2009 Nov]硬币游戏*
bzoj2017[Usaco2009 Nov]硬币游戏*
bzoj2017[Usaco2009 Nov]硬币游戏
题意：
初始时，一个有N枚硬币的堆栈放在地上，每枚硬币都有一个价值。开始玩游戏时，第一个玩家可以从堆顶拿走一枚或两枚硬币。之后每一轮中，当前的玩家至少拿走一枚硬币，至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时，游戏结束。 两个玩家都希望拿到最多钱数的硬币。求第一个玩家最多能拿多少钱。n≤2000。
题解：
首先有dp方程：f[i][j][0]=max(f[i][k][1]+sum(i-k,i)),1≤k≤min(j*2,i)，f[i][j][1]=min(f[i][k][0]),1≤k≤min(j*2,i)。
然而这样会超时。发现所以f[i][k][1]的最大值实际上是f[i][j*2][1]、f[i][j*2-1][1]、f[i][j-1][0]的最大值，f[i][k][0]的最小值也是f[i][j*2][0]、f[i][j*2-1][0]、f[i][j-1][1]的最小值。故可以把dp优化到O(n^2)可过。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 2010 6 using namespace std; 7 8 inline int read(){ 9 char ch=getchar(); int f=1,x=0;10 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}11 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();12 return f*x;13 }14 int a[maxn],sm[maxn],f[maxn][maxn][2],n;15 int main(){16 n=read(); inc(i,1,n)a[i]=read(); for(int i=n;i>=1;i--)sm[n-i+1]=sm[n-i]+a[i];17 inc(i,1,n)18 inc(j,1,n){19 f[i][j][0]=j>1?f[i][j-1][0]:0; int k;20 k=2*j-1; if(k<=i)f[i][j][0]=max(f[i][j][0],f[i-k][k][1]+sm[i]-sm[i-k]);21 k=2*j; if(k<=i)f[i][j][0]=max(f[i][j][0],f[i-k][k][1]+sm[i]-sm[i-k]);22 f[i][j][1]=j>1?f[i][j-1][1]:0x3fffffff;23 k=2*j-1; if(k<=i)f[i][j][1]=min(f[i][j][1],f[i-k][k][0]);24 k=2*j; if(k<=i)f[i][j][1]=min(f[i][j][1],f[i-k][k][0]);25 }26 printf("%d",f[n][1][0]); return 0;27 }
20160830
bzoj2017[Usaco2009 Nov]硬币游戏*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。