更新:我发现我的 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;
}
}
最佳答案
这是有效的解决方案。
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;
}
}
关于algorithm - Uva 法官 10149，Yahtzee，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6201823/