【NOJ1085】【算法实验四】【DP

1086.花生米（五）

时限：1000ms 内存限制：10000K  总时限：3000ms

描述

五一长假第六天，Tom在QQ上遇到了Kitty。呵呵，Kitty，在离散数学课上认识的PPMM……等等！Tom恍然大悟：自己这一生除了看帖不回之外最大的错误就是离散数学没学好！  五一长假第七天，Tom和Jerry在仓库散步的时候发现了一堆花生米（仓库，呵呵，仓库…）。这次Tom制定分花生米规则如下：  ???????1、首先选出最苦的一粒花生米，放到一个瓶子里；  ???????2、把剩下的花生米做成花生酱，Tom和Jerry轮流取一些花生酱吃掉；  ???????3、第一个取的人只能取1.0克，以后取花生酱的数量不能少于两个人已经取过的总数量且不能超过两个人已经取过的总数量的三倍；  ?????? 4、不能按规则3取花生酱的人必须吃掉瓶子里的花生米；  ?????? 5、为显示规则的公平性，Jerry可以选择先取或者后取。  Jerry当然希望瓶子里的花生米被Tom吃掉。请计算，Jerry为了达到目的应该先取还是后取。

 

输入

本题有多个测例，每个测例的输入是一个浮点数w，w大于1.0小于等于1000.0，w最多只有一位小数，代表花生酱的数量，单位为克。 w小于0表示输入结束，不需要处理。

 

输出

每个测例在单独的一行内输出一个整数：Jerry先取输出1；Tom先取输出0。

---

#include <iostream> using namespace std; double w; int isWin[10001]; //1==必赢，0==必输 int dp(int ate, int cur); int main() { while(cin>>w&&w>0) { for(int i=10; i<10001; i++) { isWin[i]=-1; } cout<<1-dp(10, int(w*10)-10)<<endl; //第一步只能先取10个=1克，然后让对方先取 } return 0; } int dp(int ate, int cur) { if(isWin[cur]>=0) //表中已经记录，当还剩cur个花生米时，先取是必赢还是必输 { return isWin[cur]; } if(ate>cur) //如果已取数目大于当前数目，那么此时先取必输（因为无法满足条件） { isWin[cur]=0; return isWin[cur]; } else { int isOppoWin=1; //假设自己取完之后让对方取，对方能赢 int x; for(x=ate; x<=3*ate; x++) //假设自己先取x个 { //自己取完x个，此时还剩cur-x个，让对方先取，记录此时对方是否能赢 isWin[cur-x]=dp(ate+x, cur-x); //如果还剩cur-x个时对方先取必输，那么令isOppoWin=0 isOppoWin*=isWin[cur-x]; //如果还剩cur-x个时对方先取必输，证明当自己取x个时是必赢的 if(isOppoWin==0) { break; } } //isWin[cur]=isOppoWin; //此处之前写错了，经评论指正改掉 isWin[cur] = 1 - isOppoWin; //如果对方必输，那么自己必赢；如果对方必赢，那么自己必输 return isWin[cur]; } }

---

【10.26后记】

1.这道题一开始打算记录已吃数量ate，当前还剩数量cur的状态，然而不是超时就是内存超限，无奈去网上找了代码，虽然ac了不过总感觉不对（可能是自己没看懂吧）。

2.今天突然恍然大悟，只需要用数组记录cur的状态就好，因为ate=n-cur，根本不需要记录。

3.本题思路是这样的：用数组isWin[cur]记录当前先取的人是必输还是必赢：当目前还剩下cur个花生米时，这时如果先取的人必赢，那么isWin[cur]=1，如果先取的人必输，那么isWin[cur]=0；

假设总共有w克，令n=w*10转换成整数；

在算法dp开始时，可以假设自己第一个取，只能取10个，对方第二个取，状态转换到了“还剩n-10个时对方先取”的状态，调用算法dp：

如果算法dp返回0，那么证明“还剩n-10个时对方先取”这个状态下对方是必输的，（对方第二个取必输==自己第一个取必赢），此时需要输出1代表“自己第一个取”；

如果算法dp返回1，那么证明“还剩n-10个时对方先取”这个状态下对方是必赢的，（对方第二个取必赢==自己第一个取必输）， 此时需要输出0代表“自己第二个取”，这样自己就能赢了；

这便是下面这行代码的意义：

cout<<1-dp(10, int(w*10)-10)<<endl;    //第一步只能先取10个=1克，然后让对方先取

4.在dp算法中，思路如下：

假设还剩cur个时是自己先取，那么自己可以取x个，x的范围是【ate，3*ate】，

自己取完x个之后，状态转换成”还剩cur-x个时对方先取“，记录一下isWin[cur-x]，代表在这个状态下对方先取必赢还是必输；

如果isWin[cur-x]==0，证明在”还剩cur-x个时对方先取“的状态下对方必输，于是跳出for循环，证明还剩cur个时，自己只要拿了x个就是必赢的，返回1；

如果遍历了每个x，当状态转移到对方时，对方都必赢，那么自己此时不管怎么拿都必输，返回0.