来自厦大软件工程何大佬的积分赛题目
-24点游戏
-只用加减乘除括号
-给4个数1-13的，能组成24点输出yes
-不能输出no
以上是何dalao的原话，没有截图我也很无奈
去年厦大积分赛的第一题签到题。没什么特别的方法，就是暴力求解。
最朴素的想法就是手动枚举出所有可能的情况一一判断，但是这样有可能会有错漏。
所以关于暴力的具体实现方法，我另外考虑了一个可能称得上是动规的未经确认的想法。
开一个5维的布尔型数组，前四维分别为四个数字由大到小取与不取的情况，取为1，不取为0。第五维是1到24，表示由前四维所表示的数字能否组成第五维的数字。
先将读入的四个数据分别给数组中的相应位置赋值为true，再两两进行四则运算，再将取一个与未取到这一个的取两个的数据进行四则运算，再将取一个与未取到这一个的取三个的数据进行四则运算，取两个与取另外两个的进行四则运算。最后若a[1][1][1][1][24]为true则输出yes。
这种方法有一种好处就是不会出现漏考虑的情况与出现因运算顺序出现的问题
17/12/06更新 补上我写的源代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<stdbool.h> #define MAXN 1000 int a, b, c, d; int dp[2][2][2][2][MAXN + 1]; bool endoffile = 1; int calc(int i, int j, int t) { if (t == 1)return i + j; else if (t == 2)return abs(i - j); else if (t == 3)return i*j; else if (t == 4) { if (i > j &&j != 0) { if (i%j == 0)return i / j; else return -1; } else if (i <= j && i != 0) { if (j%i == 0)return j / i; else return -1; } else return -1; } } int read() { char ch = getchar(); if (ch == EOF) { endoffile = 0; return 0; } if (ch >= 'A'&&ch <= 'Z') { char tmp = getchar(); if (tmp == EOF)endoffile = 0; if (ch == 'A')return 1; else if (ch == 'J')return 11; else if (ch == 'Q')return 12; else if (ch == 'K')return 13; } else if (ch >= '0'&&ch <= '9') { int res = 0; while (ch >= '0'&&ch <= '9') { res = res * 10 + ch - '0'; ch = getchar(); } if (ch == EOF)endoffile = 0; return res; } else return read(); } int main() { while (endoffile) { memset(dp, 0, sizeof dp); int tmp; tmp = read(); if (tmp == 0)return 0; else a = tmp; b = read(); c = read(); d = read(); //scanf("%d%d%d%d", &a, &b, &c, &d); dp[1][0][0][0][0] = 1; dp[0][1][0][0][0] = 1; dp[0][0][1][0][0] = 1; dp[0][0][0][1][0] = 1; dp[1][0][0][0][1] = a; dp[0][1][0][0][1] = b; dp[0][0][1][0][1] = c; dp[0][0][0][1][1] = d; for (int q = 2; q <= 4; q++) for (int w = 0; w <= 1; w++) for (int e = 0; e <= 1; e++) for (int r = 0; r <= 1; r++) for (int t = 0; t <= 1; t++) if (w + e + r + t == q) { for (int y = 1; y <= (1 << (q - 1)) - 1; y++) for (int u = 1; u <= dp[w == 0 ? 0 : (y >> (w - 1)) % 2][e == 0 ? 0 : (y >> (w + e - 1)) % 2][r == 0 ? 0 : (y >> (w + e + r - 1)) % 2][t == 0 ? 0 : (y >> (w + e + r + t - 1)) % 2][0]; u++) for (int i = 1; i <= dp[w == 0 ? 0 : 1 - (y >> (w - 1)) % 2][e == 0 ? 0 : 1 - (y >> (w + e - 1)) % 2][r == 0 ? 0 : 1 - (y >> (w + e + r - 1)) % 2][t == 0 ? 0 : 1 - (y >> (w + e + r + t - 1)) % 2][0]; i++) for (int o = 1; o <= 4; o++) { if (calc(dp[w == 0 ? 0 : (y >> (w - 1)) % 2][e == 0 ? 0 : (y >> (w + e - 1)) % 2][r == 0 ? 0 : (y >> (w + e + r - 1)) % 2][t == 0 ? 0 : (y >> (w + e + r + t - 1)) % 2][u], dp[w == 0 ? 0 : (1 - ((y >> (w - 1)) % 2))][e == 0 ? 0 : (1 - ((y >> (w + e - 1)) % 2))][r == 0 ? 0 : (1 - ((y >> (w + e + r - 1)) % 2))][t == 0 ? 0 : (1 - ((y >> (w + e + r + t - 1)) % 2))][i], o)==-1) continue; dp[w][e][r][t][0]++; dp[w][e][r][t][dp[w][e][r][t][0]] = calc(dp[w == 0 ? 0 : (y >> (w - 1)) % 2][e == 0 ? 0 : (y >> (w + e - 1)) % 2][r == 0 ? 0 : (y >> (w + e + r - 1)) % 2][t == 0 ? 0 : (y >> (w + e + r + t - 1)) % 2][u], dp[w == 0 ? 0 : (1 - ((y >> (w - 1)) % 2))][e == 0 ? 0 : (1 - ((y >> (w + e - 1)) % 2))][r == 0 ? 0 : (1 - ((y >> (w + e + r - 1)) % 2))][t == 0 ? 0 : (1 - ((y >> (w + e + r + t - 1)) % 2))][i], o); } } bool boo = false; for (int i = 1; i <= dp[1][1][1][1][0]; i++) if (dp[1][1][1][1][i] == 24) boo = true; if (boo) printf("1\n"); else printf("0\n"); } system("pause"); return 0; } |