Malfunctioning Typewriter

题目大意

给定$n(1\le n \le 1000)$个长度为$m(1 \le m \le 1000)$的字符串，你有一个打字机，要求你打印一个字符串，并且它是由这$n$个字符串按任意顺序连接形成的字符串之一。使用这台打字机时，你有$p(0.5 \le p \le 1)$的概率打出想要打的字符。

问采取最优策略，打印出满足要求的字符串的概率是多少？

解题思路

可以考虑建一棵字典树，那么打出一个合法字符串就相当于在这字符串上走$n$次，每走一次遍删去所对应的字符串。那么，对于字典树上的某一节点，假设它的左子树上的叶子节点数为$x$，右子树上的叶子节点数为$y$，需要保证遍历到这个节点的时候，往它的左儿子走了$x$次，右儿子走了$y$次。并且每个节点对答案的贡献都是独立的，假设节点$i$的贡献为$f[x_i][y_i]$，那么答案即为：$\prod f[x_i][y_i]$。

接下来思考如何求$f[x_i][y_i]$，自然联想到$dp$，$f[i][j]$表示打印$i$个$1$和打印$j$个$0$的概率，可得状态转移方程：

$f[i][j] = max(p * f[i - 1][j] + (1 - p)*f[i][j - 1], p * f[i][j - 1] + (1 - p)*f[i - 1][j])$

我是这样思考转转移的，考虑$f[i][j]$能转移到那些状态，如果我们打印$1$，那么有$p$的概率到$f[i + 1][j]$，有$(1 - p)$的概率到$f[i][j + 1]$；如果打印$2$，那么有$p$的概率到$f[i][j + 1]$，有$(1 - p)$的概率到$f[i + 1][j]$。

最后整合以下即可得到上式。

还有一个想法是考虑可以从哪些状态转移到当前状态，本质上感觉是差不多，笔者更习惯自己这种做法，所以这里就只介绍自己的写法了Ciallo～(∠・ω< )⌒★。

参考代码

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
#include <bits/stdc++.h>
#define maxn 1010
#define int long long
using namespace std;
const double eps = 1e-8;
double f[maxn][maxn];
int e[1000100][3], sz[1000100], idx;

void insert(string s) {
    int p = 0;
    for (auto u : s) {
        if(!e[p][u - '0'])  e[p][u - '0'] = ++idx;
        p = e[p][u - '0'];  sz[p]++;
    }
}

void solve() {
    int n, m;  double p, res = 1;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; ++i) {
        string s;  cin >> s;
        insert(s);
    }
    f[0][0] = 1;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if(i && j)  f[i][j] = max(p * f[i - 1][j] + (1.0 - p) * f[i][j - 1], p * f[i][j - 1] + (1.0 - p) * f[i - 1][j]);
            else if(i)  f[i][j] = max(p * f[i - 1][j], (1.0 - p) * f[i - 1][j]);
            else if(j)  f[i][j] = max((1.0 - p) * f[i][j - 1], p * f[i][j - 1]);
        }
    }
    for (int i = 0; i < idx; ++i)  res *= f[sz[e[i][0]]][sz[e[i][1]]];
    cout << fixed << setprecision(10) << res << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}