题目：
题目大意：题目好长>_<。大致是说有一个游戏，有n列，每列最多6个方块，这些方块是垂直放的如果下面没有东西了就会垂 直掉下来（初始方块的状态有限制条件不过这题没用）。现在有两个人玩游戏，他们各有一支枪，每发子弹的攻击力为1、2或3，概率均为1/3。可以选择从左 攻击或从右攻击，可以自己选择一行，发射子弹之后最多打掉子弹攻击力个方块（如果子弹攻击力比方块多，那么就只有浪费掉了），然后悬浮的方块会往下掉。现 在这两个人都足够聪明，每次都会选择胜率最高的来开枪，问先手的胜率。
思路：容易看出状态数最多有7^6=117649种，记忆化搜索可以解决（我总觉得这是暴力求破）。分别计算从左边六行发射子弹的胜 率，再计算右边六行发射子弹的胜率，取最大的一个（这玩游戏的人真是神智商，你以为个个都是冯洛伊曼吗……）。用dp[x1][x2][x3][x4] [x5][x6]来记录一个人面临第一列x1个，第二列x2个……的状态的胜率即可。注意处理细节还是比较容易AC的。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef long long LL; 8 #define FOR(i, s, t) for(int i = s; i <= t; ++i) 9 10 const int MAXS = 50010;11 const int MAXN = 8;12 const double EPS = 1e-8;13 14 double a[7][7][7][7][7][7];15 16 double solve(int p1, int p2, int p3, int p4, int p5, int p6) {17 if(a[p1][p2][p3][p4][p5][p6] > EPS) return a[p1][p2][p3][p4][p5][p6];18 if(p1 + p2 + p3 + p4 + p5 + p6 == 0) return 0;19 int v1, v2, v3, v4, v5, v6;20 double ret = 0;21 for(int i = 1; i <= 6; ++i) {22 double tmp = 0;23 for(int j = 1; j <= 3; ++j) {24 v1 = p1, v2 = p2, v3 = p3, v4 = p4, v5 = p5, v6 = p6;25 int k = j;26 if(v1 >= i && k) --v1, --k;27 if(v2 >= i && k) --v2, --k;28 if(v3 >= i && k) --v3, --k;29 if(v4 >= i && k) --v4, --k;30 if(v5 >= i && k) --v5, --k;31 if(v6 >= i && k) --v6, --k;32 if(k == j) continue;33 tmp += 1./3 * (1 - solve(v1, v2, v3, v4, v5, v6));34 }35 if(tmp > ret) ret = tmp;36 tmp = 0;37 for(int j = 1; j <= 3; ++j) {38 v1 = p1, v2 = p2, v3 = p3, v4 = p4, v5 = p5, v6 = p6;39 int k = j;40 if(v6 >= i && k) --v6, --k;41 if(v5 >= i && k) --v5, --k;42 if(v4 >= i && k) --v4, --k;43 if(v3 >= i && k) --v3, --k;44 if(v2 >= i && k) --v2, --k;45 if(v1 >= i && k) --v1, --k;46 if(k == j) continue;47 tmp += 1./3 * (1 - solve(v1, v2, v3, v4, v5, v6));48 }49 if(tmp > ret) ret = tmp;50 }51 return a[p1][p2][p3][p4][p5][p6] = ret;52 }53 54 int x[7], n;55 56 int main() {57 //FOR(i1, 0, 6) FOR(i2, 0, 6) FOR(i3, 0, 6) FOR(i4, 0, 6) FOR(i5, 0, 6) FOR(i6, 0, 6)58 //if(a[i1][i2][i3][i4][i5][i6] < EPS) solve(i1, i2, i3, i4, i5, i6);59 while(scanf("%d", &n) != EOF && n) {60 memset(x, 0, sizeof(x));61 for(int i = 1; i <= n; ++i) scanf("%d", &x[i]);62 printf("%.6f\n", solve(x[1], x[2], x[3], x[4], x[5], x[6]));63 }64 }