【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+1P

直接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=,P=,M=*;

int lst[M],nxt[M];
ll p[N],t[M];
int n,l,a[N][],b[N];
db eps=,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 -;
}

int get(int a,int b,int c) {
    if (a>c) swap(a,c);
    return (((a<<)+b)<<)+c;
}

ll get_ha() {
    ll ha=;
    fo(i,,n-) if (a[i][]&&b[i]>) p[i]=get(a[i][],a[i][],a[i][]); 
    else p[i]=;
    p[n]=get(a[n][],a[n][],a[n][]);
    sort(p+,p+n);
    fo(i,,n) ha=ha*P+p[i];
    return ha;
}

db dfs() {
    ll ha=get_ha();
    db now=find(ha%M,ha);
    if (now!=-) return now;

    db ans=;
    db c[]={,,,};
    db P=/;
    fo(cl,,)
        fo(i,,n-)
            fo(j,,) {
                bool ok=a[i][j]==cl;
                if (b[i]==) ok=;
                if (j!=&&!a[i][]) ok=;
                if (j==&&b[i]!=) ok=;
                if (ok) {
                    bool pd=;
                    if (b[n]==) {n++;pd=;}
                    a[i][j]=;b[i]--;
                    fo(k,,) 
                        if (a[n][k]==) {
                            a[n][k]=cl;b[n]++;
                            c[cl]=min(c[cl],dfs());
                            a[n][k]=;b[n]--;
                        }
                    if (pd) n--;
                    a[i][j]=cl;b[i]++;
                }
            }
    if (c[]==) {c[]=;P+=/;}
    if (c[]==) {c[]=;P+=/;}
    if (c[]==) {c[]=;P+=/;}
    if (fabs(P-)<eps) return ;
    ans=ans+c[]/+c[]/+c[]/;
    ans=ans/(-P);

    if (find(ha%M,ha)==-) add(ha%M,ha,ans);
    return ans;
}

int main() {
    scanf("%d",&n);
    fo(i,,n) {
        char ch;b[i]=;
        for(ch=getchar();ch<'A'||ch>'Z';ch=getchar());
        fo(j,,) {
            if (ch=='G') a[i][j]=;
            if (ch=='B') a[i][j]=;
            if (ch=='R') a[i][j]=;
            ch=getchar();
        }
    }
    printf("%.9lf\n",dfs());
}