题解 P1837 【单人纸牌】

zimujun · 2020-10-24 19:39:24 · 题解

写在前面

感谢巨佬 yu__xuan 的帮助！
原本题解区的大佬们大都写的九层循环，其实此题如果写成状压，可以将这九层循环写成一层，非但简洁、代码可读性强，常数也比直接九维 dp 小。

算法思路

由于每一行都只有四张牌，考虑写成五进制状压 dp。

设当前状态为 t，则五进制状压 dp 取出第 i 行的状态的方式:\frac{t}{5^i}\!\!\!\!\mod 5（视初始行为第 0 行）

因此，若设第 i 行的第 j 张牌的点数为 a_{i,j},则状态转移方程为：

\large f_{t - 5^{p1} - 5^{p2}} = f_{t - 5^{p1} - 5^{p2}} + f_t \times p(a_{p1,\frac{t}{5^p1}\!\!\!\!\mod 5} = a_{p2,\frac{t}{5^p2}\!\!\!\!\mod 5})

其中 p 为此次转移的概率，等于从状态 t 能转移到的状态数总和的倒数。

边界条件: f_{5^9 - 1} = 1。

倒序枚举所有状态，每当找到一个当前答案不为 0 的状态时，先统计出它能更新到的状态数，算出转移的概率 P，然后用该状态去更新它所能更新到的状态的答案。

由于一直在拿牌，表示状态的变量会逐渐减小，倒序枚举状态时可行的。

Tips

读入的时候用类似于快速读入的方式过滤一下不合法字符可以极大地简化读入部分的代码。
扑克牌的点数不等同于真实的扑克牌的点数，因此统计的时候不需要再对点数进行处理，直接将 char 转成 int 存下来即可。

Code

#include<bits/stdc++.h>
#define LF double

const int pow5[] = {1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125}; 
using namespace std;

LF f[1953125];
int a[10][5];

char Getch() {char ch = getchar(); while((!isalpha(ch)) && (!isdigit(ch))) ch = getchar(); return ch;}

int main() {
    for(register int i = 0; i < 9; ++i) {
        for(register int j = 1; j <= 4; ++j) {
            a[i][j] = Getch(); Getch();
        }
    }
    f[1953124] = 1.0;
    for(register int t = pow5[9] - 1; t >= 0; --t) {
        if(f[t] == 0) continue;
        LF choise = 0;
        for(register int p1 = 0; p1 < 9; ++p1) {
            for(register int p2 = p1 + 1; p2 < 9; ++p2) {
                if((a[p1][t / pow5[p1] % 5] == a[p2][t / pow5[p2] % 5]) && ((t / pow5[p1] % 5) > 0) && ((t / pow5[p2] % 5) > 0)) choise++;
            }
        }
        LF P = f[t] * 1.0 / choise;
        for(register int p1 = 0; p1 < 9; ++p1) {
            for(register int p2 = p1 + 1; p2 < 9; ++p2) {
                if((a[p1][t / pow5[p1] % 5] == a[p2][t / pow5[p2] % 5]) && ((t / pow5[p1] % 5) > 0) && ((t / pow5[p2] % 5) > 0)) {
                    f[t - pow5[p1] - pow5[p2]] += P;
                }
            }
        }
    }
    printf("%lf", f[0]);
    return 0; 
}