[书法家](https://www.luogu.org/problemnew/show/P1398)了解一下
by GKxx @ 2018-09-18 22:38:57
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
#define re register
using namespace std;
int cnt,f[10];
double dp[5][5][5][5][5][5][5][5][5];
char a[1001][10];
int main()
{
for (re int x=1;x<=9;x++)
{
for (re int i=4;i;--i)
{
re char s[10];
scanf("%s",s+1);
a[x][i]=s[1];
}
}
dp[0][0][0][0][0][0][0][0][0]=1;
for(f[1]=0;f[1]<=4;f[1]++)
for(f[2]=0;f[2]<=4;f[2]++)
for(f[3]=0;f[3]<=4;f[3]++)
for(f[4]=0;f[4]<=4;f[4]++)
for(f[5]=0;f[5]<=4;f[5]++)
for(f[6]=0;f[6]<=4;f[6]++)
for(f[7]=0;f[7]<=4;f[7]++)
for(f[8]=0;f[8]<=4;f[8]++)
for(f[9]=0;f[9]<=4;f[9]++)
if(dp[f[1]][f[2]][f[3]][f[4]][f[5]][f[6]][f[7]][f[8]][f[9]])
{
re double p=dp[f[1]][f[2]][f[3]][f[4]][f[5]][f[6]][f[7]][f[8]][f[9]];
re int cnt=0;
for(re int x=1;x<9;x++)
for(re int y=x+1;y<=9;y++)
if(f[x]+1<=4&&f[y]+1<=4&&a[x][f[x]+1]==a[y][f[y]+1]) cnt++;
if(cnt>0)
for (re int x=1;x<9;x++)
for (re int y=x+1;y<=9;y++)
if (f[x]+1<=4&&f[y]+1<=4&&a[x][f[x]+1]==a[y][f[y]+1])
{
f[x]++;f[y]++;
dp[f[1]][f[2]][f[3]][f[4]][f[5]][f[6]][f[7]][f[8]][f[9]]+=p/(double)(cnt*1.0);
f[x]--;f[y]--;//回溯
}
}
printf("%.6lf",dp[4][4][4][4][4][4][4][4][4]);
}
```
(同上↑)
机房同学们都是用记忆化搜索的。。。
by 乌合之众 @ 2018-09-18 22:47:18
害怕上面大佬
by 反比例函数 @ 2018-09-18 22:51:14
@[GKxx](/space/show?uid=72071) %%%黑题大佬
by nosta @ 2018-09-19 07:50:29