Uva Judge 10149，Yahtzee

Question

更新：我发现我的 DP 解决方案无法正确处理奖金的问题。我向状态数组添加了一个维度来表示前 6 个类别的总和。然而，解决方案超时了。这并不是严重的超时，因为在我的机器上每个测试用例可以在不到 1 秒的时间内解决。

问题描述在这里： http://uva.onlinejudge.org/external/101/10149 .html

网上搜了一下，发现应该是通过DP和bitmask来解决。我实现了代码并通过了我测试的所有测试用例，但 Uva Judge 返回了错误的答案。

我的想法是让 state[i][j] 将 i 轮匹配到由 j 位掩码的类别。请指出我的错误或链接一些可以正确解决此问题的代码。这是我的代码：

public class P10149 {

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        // Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            int[][] round = new int[13][5];
            for (int i = 0; i < 13; i++) {
                for (int j = 0; j < 5; j++) {
                    round[i][j] = in.nextInt();
                }
            }
            in.nextLine();
            int[][] point = new int[13][13];
            for (int i = 0; i < 13; i++) {
                for (int j = 0; j < 13; j++) {
                    point[i][j] = getPoint(round[i], j);
                }
            }

            int[][] state = new int[14][1 << 13];
            for (int i = 1; i <= 13; i++) {
                Arrays.fill(state[i], -1);
            }
            int[][] bonusSum = new int[14][1 << 13];
            int[][] choice = new int[14][1 << 13];
            for (int i = 1; i <= 13; i++) {
                for (int j = 0; j < (1 << 13); j++) {
                    int usedSlot = 0;
                    for (int b = 0; b < 13; b++) {
                        if (((1 << b) & j) != 0) {
                            usedSlot++;
                        }
                    }
                    if (usedSlot != i) {
                        continue;
                    }
                    for (int b = 0; b < 13; b++) {
                        if (((1 << b) & j) != 0) {
                            int j2 = (~(1 << b) & j);
                            int bonus;
                            if (b < 6) {
                                bonus = bonusSum[i - 1][j2] + point[i - 1][b];
                            } else {
                                bonus = bonusSum[i - 1][j2];
                            }
                            int newPoint;
                            if (bonus >= 63 && bonusSum[i - 1][j2] < 63) {
                                newPoint = 35 + state[i - 1][j2] + point[i - 1][b];
                            } else {
                                newPoint = state[i - 1][j2] + point[i - 1][b];
                            }
                            if (newPoint > state[i][j]) {
                                choice[i][j] = b;
                                state[i][j] = newPoint;
                                bonusSum[i][j] = bonus;
                            }
                        }
                    }
                }
            }

            int index = (1 << 13) - 1;
            int maxPoint = state[13][index];
            boolean bonus = (bonusSum[13][index] >= 63);
            int[] mapping = new int[13];
            for (int i = 13; i >= 1; i--) {
                mapping[choice[i][index]] = i;
                index = (~(1 << choice[i][index]) & index);
            }

            for (int i = 0; i < 13; i++) {
                System.out.print(point[mapping[i] - 1][i] + " ");
            }
            if (bonus) {
                System.out.print("35 ");
            } else {
                System.out.print("0 ");
            }
            System.out.println(maxPoint);
        }
    }

    static int getPoint(int[] round, int category) {
        if (category < 6) {
            int sum = 0;
            for (int i = 0; i < round.length; i++) {
                if (round[i] == category + 1) {
                    sum += category + 1;
                }
            }
            return sum;
        }
        int sum = 0;
        int[] count = new int[7];
        for (int i = 0; i < round.length; i++) {
            sum += round[i];
            count[round[i]]++;
        }
        if (category == 6) {
            return sum;
        } else if (category == 7) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 3) {
                    return sum;
                }
            }
        } else if (category == 8) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 4) {
                    return sum;
                }
            }
        } else if (category == 9) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 5) {
                    return 50;
                }
            }
        } else if (category == 10) {
            for (int i = 1; i <= 3; i++) {
                if (isStraight(count, i, 4)) {
                    return 25;
                }
            }
        } else if (category == 11) {
            for (int i = 1; i <= 2; i++) {
                if (isStraight(count, i, 5)) {
                    return 35;
                }
            }
        } else if (category == 12) {
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= 6; j++) {
                    if (i != j && count[i] == 3 && count[j] == 2) {
                        return 40;
                    }
                }
            }
        }
        return 0;
    }

    static boolean isStraight(int[] count, int start, int num) {
        for (int i = start; i < start + num; i++) {
            if (count[i] == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 1

这是工作解决方案。

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class P10149 {

    static final int MAX_BONUS_SUM = 115;

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        // Scanner in = new Scanner(System.in);
        long t1 = System.currentTimeMillis();
        while (in.hasNextLine()) {
            int[][] round = new int[13][5];
            for (int i = 0; i < 13; i++) {
                for (int j = 0; j < 5; j++) {
                    round[i][j] = in.nextInt();
                }
            }
            in.nextLine();
            int[][] point = new int[13][13];
            for (int i = 0; i < 13; i++) {
                for (int j = 0; j < 13; j++) {
                    point[i][j] = getPoint(round[i], j);
                }
            }

            int[][] state = new int[1 << 13][MAX_BONUS_SUM + 1];
            int[][] newState = new int[1 << 13][MAX_BONUS_SUM + 1];
            for (int j = 0; j < (1 << 13); j++) {
                Arrays.fill(state[j], -1);
                Arrays.fill(newState[j], -1);
            }
            state[0][0] = 0;
            int[][][] choice = new int[13][1 << 13][MAX_BONUS_SUM + 1];
            for (int i = 0; i < 13; i++) {
                for (int j = 0; j < (1 << 13); j++) {
                    int usedSlot = 0;
                    for (int b = 0; b < 13; b++) {
                        if (((1 << b) & j) != 0) {
                            usedSlot++;
                        }
                    }
                    if (usedSlot != i + 1) {
                        continue;
                    }
                    for (int b = 0; b < 13; b++) {
                        if (((1 << b) & j) != 0) {
                            int j2 = (~(1 << b) & j);
                            for (int s = 0; s <= MAX_BONUS_SUM; s++) {
                                int oldSum;
                                if (b < 6) {
                                    if (s < point[i][b]) {
                                        s = point[i][b] - 1;
                                        continue;
                                    }
                                    oldSum = s - point[i][b];
                                } else {
                                    oldSum = s;
                                }
                                if (state[j2][oldSum] < 0) {
                                    continue;
                                }
                                int newPoint;
                                if (s >= 63 && oldSum < 63) {
                                    newPoint = 35 + state[j2][oldSum] + point[i][b];
                                } else {
                                    newPoint = state[j2][oldSum] + point[i][b];
                                }
                                if (newPoint > newState[j][s]) {
                                    choice[i][j][s] = b;
                                    newState[j][s] = newPoint;
                                }
                            }
                        }
                    }
                }

                for (int j = 0; j < (1 << 13); j++) {
                    for (int s = 0; s <= MAX_BONUS_SUM; s++) {
                        state[j][s] = newState[j][s];
                    }
                    Arrays.fill(newState[j], -1);
                }
            }

            int index = (1 << 13) - 1;
            int maxPoint = -1;
            int sum = 0;
            for (int s = 0; s <= MAX_BONUS_SUM; s++) {
                if (state[index][s] > maxPoint) {
                    maxPoint = state[index][s];
                    sum = s;
                }
            }

            boolean bonus = (sum >= 63);
            int[] mapping = new int[13];
            for (int i = 12; i >= 0; i--) {
                mapping[choice[i][index][sum]] = i;
                int p = 0;
                if (choice[i][index][sum] < 6) {
                    p = point[i][choice[i][index][sum]];
                }
                index = (~(1 << choice[i][index][sum]) & index);
                sum -= p;
            }

            for (int i = 0; i < 13; i++) {
                System.out.print(point[mapping[i]][i] + " ");
            }
            if (bonus) {
                System.out.print("35 ");
            } else {
                System.out.print("0 ");
            }
            System.out.println(maxPoint);
        }
        long t2 = System.currentTimeMillis();
        // System.out.println(t2 - t1);
    }

    static int getPoint(int[] round, int category) {
        if (category < 6) {
            int sum = 0;
            for (int i = 0; i < round.length; i++) {
                if (round[i] == category + 1) {
                    sum += category + 1;
                }
            }
            return sum;
        }
        int sum = 0;
        int[] count = new int[7];
        for (int i = 0; i < round.length; i++) {
            sum += round[i];
            count[round[i]]++;
        }
        if (category == 6) {
            return sum;
        } else if (category == 7) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 3) {
                    return sum;
                }
            }
        } else if (category == 8) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 4) {
                    return sum;
                }
            }
        } else if (category == 9) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 5) {
                    return 50;
                }
            }
        } else if (category == 10) {
            for (int i = 1; i <= 3; i++) {
                if (isStraight(count, i, 4)) {
                    return 25;
                }
            }
        } else if (category == 11) {
            for (int i = 1; i <= 2; i++) {
                if (isStraight(count, i, 5)) {
                    return 35;
                }
            }
        } else if (category == 12) {
            for (int i = 1; i <= 6; i++) {
                if (count[i] >= 5) {
                    return 40;
                }
            }
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= 6; j++) {
                    if (i != j && count[i] == 3 && count[j] == 2) {
                        return 40;
                    }
                }
            }
        }
        return 0;
    }

    static boolean isStraight(int[] count, int start, int num) {
        for (int i = start; i < start + num; i++) {
            if (count[i] == 0) {
                return false;
            }
        }
        return true;
    }
}

Answer 2

使用Munker算法来解决这个问题