版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434720
详细代码可以fork下Github上leetcode项目,不定期更新。
练习题如下:
翻译参考:http://www.hankcs.com/program/algorithm/poj-3688-cheat-in-the-game.html
金手指:有俩人玩一个取石子的游戏,你是裁判。游戏中有W块石头和N张卡片,卡片上分别写着数字Ai。玩家随机抽走一张卡片,按卡片上的数字从石头堆中取走相应数量的石头,如果石头不够,玩家重新抽卡片,取走最后一块石头的玩家获胜;如果石头堆为空仍然未分出胜负,则拿回所有石头和卡片重新开始。 现在先手玩家贿♂赂了你,请你帮他构造必胜条件。游戏中的卡片是固定的,但W可供你操作。问有多少小于或等于M的W满足要求。
思路:
嗯哼,题目中有个要求,如果W有剩余,那么将重新比赛,这就意味着,给定的W一定能够由这些卡片的数值组成。那么问题就转换成,求解偶数张卡片可能组成的集合A,和奇数张卡片可能组成的集合B,并且集合B中不允许有集合A的元素,否则对于Alice来说不是必胜策略。
所以trick在于如何表示集合B中是否存在集合A的元素呢?传统的想法是dpM ,表示M是否能够由这些卡片组合,现在需要多一维状态。
dp[m][2]:
dp[m][0] 表示由偶数张卡片组成和M
dp[m][1] 表示由奇数张卡片组成和M
Alice 必胜策略为:
dp[m][0] = false && dp[m][1] = true
状态转移:
如果当前状态为偶数张卡片组成的和,则下一状态为奇数张卡片组成的和
代码如下:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
String INPUT = "./data/judge/201709/P3688.txt";
public static void main(String[] args) throws IOException {
new Main().run();
}
static final int MAX_M = 100000 + 16;
boolean[][] dp = new boolean[MAX_M][2];
void solve() {
while (true) {
int n = ni();
int m = ni();
if (n == 0 && m == 0) break;
if (n == 0) {
out.println("0");
continue;
}
int[] cards = new int[n];
for (int i = 0; i < n; ++i) {
cards[i] = ni();
}
dp = new boolean[MAX_M][2];
dp[cards[0]][1] = true;
for (int i = 1; i < n; ++i) {
for (int j = m; j > cards[i]; --j) {
if (dp[j - cards[i]][0]) {
dp[j][1] = true;
}
if (dp[j - cards[i]][1]) {
dp[j][0] = true;
}
}
dp[cards[i]][1] = true;
}
int ans = 0;
for (int i = 1; i <= m; ++i) {
if (dp[i][1] && !dp[i][0]) ans ++;
}
out.println(ans);
}
}
FastScanner in;
PrintWriter out;
void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}
InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}
public boolean more(){
return in.hasNext();
}
public int ni(){
return in.nextInt();
}
public long nl(){
return in.nextLong();
}
public double nd(){
return in.nextDouble();
}
public String ns(){
return in.nextString();
}
public char nc(){
return in.nextChar();
}
class FastScanner {
BufferedReader br;
StringTokenizer st;
boolean hasNext;
public FastScanner(InputStream is) throws IOException {
br = new BufferedReader(new InputStreamReader(is));
hasNext = true;
}
public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}
String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}
public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}
public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}
public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}
public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}
public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}