挑战程序竞赛系列（50）：4.2 推理与动态规划算法（3）

用户1147447

发布于 2019-05-26 09:42:15

2650

发布于 2019-05-26 09:42:15

文章被收录于专栏：机器学习入门机器学习入门机器学习入门

挑战程序竞赛系列（50）：4.2 推理与动态规划算法（3）

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 3688: Cheat in the Game

POJ 3688: Cheat in the Game

翻译参考：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);
        }
    }
}