Posted on 2009-11-12 00:20
rikisand 阅读(436)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm 、
USACO
周六第一次做usaco玩，bronze的轻松切掉，然后申请promote，下午批准，话说rob 效率好高啊~ 于是继续做silver 就遇到这个题- -！纠结了半天放弃····知道是dp 也考虑了方法就是 理不清楚；不知道是不是一天没吃饭的缘故·····
今天题解出来了~ 先看了大概思路 然后自己写出来了~
题目：
Farmer John's cows like to play coin games so FJ has invented with
a new two-player coin game called Xoinc for them.
Initially a stack of N (5 <= N <= 2,000) coins sits on the ground;
coin i from the top has integer value C_i (1 <= C_i <= 100,000).
The first player starts the game by taking the top one or two coins
(C_1 and maybe C_2) from the stack. If the first player takes just
the top coin, the second player may take the following one or two
coins in the next turn. If the first player takes two coins then
the second player may take the top one, two, three or four coins
from the stack. In each turn, the current player must take at least
one coin and at most two times the amount of coins last taken by
the opposing player. The game is over when there are no more coins
to take.
Afterwards, they can use the value of the coins they have taken
from the stack to buy treats from FJ, so naturally, their purpose
in the game is to maximize the total value of the coins they take.
Assuming the second player plays optimally to maximize his own
winnings, what is the highest total value that the first player can
have when the game is over?
MEMORY LIMIT: 20 MB
PROBLEM NAME: xoinc
INPUT FORMAT:
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: C_i
SAMPLE INPUT (file xoinc.in):
5
1
3
1
7
2
简单来说就是两个人轮流取coins，每个人每次取得个数为1- 2*n;n为上一轮对方取得数目，
求两个人都是用最佳策略，先取得那个家伙最多能拿到多少硬币。貌似可以算是简单博弈论的思想
思路：
coins[1···N] 从下到上 sum[1···N] 剩下 i个的和
找到无后效性的子问题。考虑在还剩下p个钱币时候的情况，此时可以拿k个钱
由于条件，k的大小受上一轮拿的个数i的限制 ，所以我们要加上一个变量i。得到
dp[p][i]这个子问题。那么容易得到
dp[p][i]=max(1=<k<=i*2){SuM(p to p-k+1)+SuM(p-k to 1)-dp[p-k][k]} =max(1=<k<=i*2){sum[p]-dp[p-k][k]}按照这个可以得到一个O（N^3）的算法
oidsolve(){
for(inti=1;i<=N;i++)//剩下i个
for(intj=1;j<=N;j++)//上一人拿了j 个
for(intk=1;k<=j*2&&i-k>=0;k++){
dp[i][j]=max(dp[i][j],sum[1]-sum[i+1]-dp[i-k][k]);
}
ret=dp[N][1];
}
三重递归 ，最多可以过500的数据量 观察可以得出 dp[p][j] 和 dp[p][j+1] 的计算有很多的重叠
因为 上次拿了j+1 则可以比 dp[p][j] 多拿 2 个
然后，由于考虑j的范围 应该为 N-i+1
这样得到了最终代码：
scanf("%d",&N);
for(int i=1;i<=N;i++) scanf("%d",coins+i);//{fin>>coins[i]; }
sum[0]=0;
for(int i=1;i<=N;i++) sum[i]=sum[i-1]+coins[N-i+1];
for(int i=1;i<=N;i++) //剩下i个
for(int j=1;j<= N-i +1;j++){ // 上次拿了j个
if(dp[i][j]<dp[i][j-1])dp[i][j]=dp[i][j-1];
if(2*j-1<=i&&dp[i][j]<sum[i]-dp[i-2*j+1][2*j-1]) dp[i][j]=sum[i]-dp[i-2*j+1][2*j-1];
if(2*j<=i&&dp[i][j]<sum[i]-dp[i-2*j][2*j]) dp[i][j]= sum[i]-dp[i-2*j][2*j];
}
printf("%d\n",dp[N][1]);
很晚了 ，先写这么多 ，有空把bronze的写了
3个月后注：事实证明，当时么有时间 ~以后更没有时间 ~~~ hoho`````````~~~~~~~``````````