【CF424E】Colored Jenga

Description

Tomsk 寒冷的冬季傍晚非常无聊——没人想要在这个时间点儿上在街上晃。居住在Tomsk 的市民都坐在温暖的公寓里玩游戏打发时间。他们玩的其中一个游戏唤作“有色积木” 。

这个游戏需要三种不同颜色的木块：红色，绿色及蓝色。接着，用这些积木堆出一座n 层的塔。塔中每一层由三块积木组成。虽然这些组成塔的积木可以是三色中的任意一种颜色，但是它们必须平行且紧密排列。本文图中作为样例展示了一座塔。

游戏的玩家有且仅有恰好一人。每一分钟，玩家扔一次一个特殊的六面骰子。这个骰子有两面是绿色的，两面是蓝色的，一面红色及一面黑色。滚动结束后六面在最上面的机率相等。

如果滚出红色，绿色或蓝色，那么在这一分钟内，在塔中抽出一块这种颜色的积木，同时让塔不倒。如果这不可能，那么玩家需等到这分钟结束，且不触碰积木塔。同样，如果滚出黑色，那么亦要不触碰积木塔直至这分钟结束。另外，无论如何，从最上面的一层抽取积木是不被允许的。

一旦玩家抽出了一个积木，他必须把它放在塔的顶端，形成新的一层或填充最顶层。新堆出的一层需拥有和初始的若干层相同的性质。如果顶层没有填满，则禁止形成新的一层。

为了让塔不至于倒下，在除了顶层的每一层中，至少要有一块积木。此外，如果在某些层里，只留下了一块积木，且不是中间的那块，那么塔倒下。

当抽出任意一个非顶层的积木都会使塔倒下的时候，游戏结束。

这是由Tomsk 市民创造的奇妙游戏之一。我很想知道，当玩家始终做出完美的决策时，游戏会持续多少分钟。如果玩家的决策完美，那么每时每刻他选择抽出令游戏结束的期望时间最短的积木。

你的任务是写出一个程序，确定游戏结束期望需要多少分钟。
n<=6

Solution

考虑状压，设当前状态为S，可转移到的状态为SG，SR，SB（如果不能转移到就是0）
并且这一步可以转移的概率是P，那么我们可以得出

$$F(S)={F(SG)/3+F(SB)/3+F(SR)/6+1}\over P$$
直接Dp的状态数有点多，我们可以考虑优化本质相同的状态。
1”行与行之间是独立的（除了最后一行），于是我们可以把每一行的状态排序之后再哈希，也就是最小表示。
2”左边的块和右边的块也是一样的，对每一行也可以最小表示来优化状态。
3”如果某一行不能取了，我们就忽略这一行的状态，显然所有这样的状态的答案就是一样的。
这样就能有效优化无用的状态，足以在限定时限内通过本题。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a) for(int i=lst[a];i;i=nxt[i])
using namespace std;typedef unsigned long long ll;
typedef double db;const int N=30,P=67,M=4*1e6;int lst[M],nxt[M];
ll p[N],t[M];
int n,l,a[N][4],b[N];
db eps=1e-6,f[M];void add(int x,ll y,db z) {t[++l]=y;f[l]=z;nxt[l]=lst[x];lst[x]=l;
}db find(int x,ll y) {rep(i,x) if (t[i]==y) return f[i];return -1;
}int get(int a,int b,int c) {if (a>c) swap(a,c);return (((a<<2)+b)<<2)+c;
}ll get_ha() {ll ha=0;fo(i,1,n-1) if (a[i][2]&&b[i]>1) p[i]=get(a[i][1],a[i][2],a[i][3]); else p[i]=0;p[n]=get(a[n][1],a[n][2],a[n][3]);sort(p+1,p+n);fo(i,1,n) ha=ha*P+p[i];return ha;
}db dfs() {ll ha=get_ha();db now=find(ha%M,ha);if (now!=-1) return now;db ans=1.0;db c[4]={0,1e9,1e9,1e9};db P=1.0/6.0;fo(cl,1,3)fo(i,1,n-1)fo(j,1,3) {bool ok=a[i][j]==cl;if (b[i]==1) ok=0;if (j!=2&&!a[i][2]) ok=0;if (j==2&&b[i]!=3) ok=0;if (ok) {bool pd=0;if (b[n]==3) {n++;pd=1;}a[i][j]=0;b[i]--;fo(k,1,3) if (a[n][k]==0) {a[n][k]=cl;b[n]++;c[cl]=min(c[cl],dfs());a[n][k]=0;b[n]--;}if (pd) n--;a[i][j]=cl;b[i]++;}}if (c[1]==1e9) {c[1]=0;P+=1.0/3.0;}if (c[2]==1e9) {c[2]=0;P+=1.0/3.0;}if (c[3]==1e9) {c[3]=0;P+=1.0/6.0;}if (fabs(P-1)<eps) return 0;ans=ans+c[1]/3.0+c[2]/3.0+c[3]/6.0;ans=ans/(1-P);if (find(ha%M,ha)==-1) add(ha%M,ha,ans);return ans;
}int main() {scanf("%d",&n);fo(i,1,n) {char ch;b[i]=3;for(ch=getchar();ch<'A'||ch>'Z';ch=getchar());fo(j,1,3) {if (ch=='G') a[i][j]=1;if (ch=='B') a[i][j]=2;if (ch=='R') a[i][j]=3;ch=getchar();}}printf("%.9lf\n",dfs());
}