OI Problems   关于

状态压缩动态规划

仔细观察可以发现以下几点:

结论 1:有效层总数不会超过 n+1n+1

若一层中只有中间的位置有木板或者两边的位置有木板,则此层事实上已经没有实际用处,不妨删除该层。塔的下部每层至多抽出 22 块后该层无效,而在上部添加一层需要 33 块木板。

结论 2:任意两层非顶层的有效层,可以任意交换。(这是显然的)

结论 3:任意一层有效层的左右两个位置对称,可以交换。(这也是显然的)

考虑状态压缩。

对于一个塔的状态,每一层一个位置有四种状态:放置了木板(三种颜色),以及没有放置木板。而每一层有三个位置,需要占用 66 个二进制位。对于一个塔的状态,有效层至多 n+17n+1\leq 7 层,即至多占用 6×7=426\times 7=42 个二进制位,只需使用 unsigned long long 存储即可。

每一次状态转移枚举投掷出的三种颜色(投掷出黑色的情况可以 Θ(1)\Theta(1) 处理),再枚举删除的是哪一块该色木板,最后枚举放置在顶层的哪个位置即可。

具体细节见代码实现。

  代码
// 2022.07.04

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n,a[100][4],t[100];

struct Node{
    // 状态结构体
    ull value;
    double p;
    int nxt;
}node[5000000];
int head[5000000],cnt; // 对状态模 5e6 的余数使用链式前向星存储

inline ull gethash(){
    // 计算当前状态的哈希值
    for(int i=1;i<=n;i++){
        t[i]=0;
        if(i!=n&&(!a[i][2]||(!a[i][1]&&!a[i][3])))continue; // 遇到无效层
        bool flag=false;
        if(a[i][1]>a[i][3])
            swap(a[i][1],a[i][3]),flag=true; // 等价交换
        for(int j=1;j<=3;j++)
            t[i]|=a[i][j]<<(j-1<<1); // 状态压缩计算
        if(flag)swap(a[i][1],a[i][3]); // 换回去
    }
    sort(t+1,t+n); // 对除了顶层的状态压缩值进行排序
    ull tmp=0;
    for(int i=1;i<=n;i++)
        if(t[i])tmp<<=6,tmp|=t[i]; // 计算最终哈希值
    return tmp;
}
inline int getid(ull val){
    int headid=val%5000000;
    for(int i=head[headid];i;i=node[i].nxt)
        if(node[i].value==val)return i; // 找到该状态,返回 id
    // 没有找到该状态,将状态加入列表中
    node[++cnt]={val,-1,head[headid]};
    head[headid]=cnt;
    return cnt;
}

double dfs(ull now){
    int id=getid(now);
    if(node[id].p>=0)return node[id].p;
    double error=1/6.0,sum=0;
    for(int color=1;color<=3;color++){ // 枚举颜色
        double p=1.0/(color==1?6:3),minn=1e10;
        // p: 该颜色权重,即出现概率
        for(int i=1;i<n;i++)
            for(int j=1;j<=3;j++){
                if(a[i][j]!=color)continue;
                if(j==2&&(!a[i][1]||!a[i][3]))continue; // 删除后塔不符合条件,故退出
                if(j!=2&&!a[i][2])continue; // 删除后塔不符合条件,故退出
                a[i][j]=0;
                bool flag=false;
                if(a[n][1]&&a[n][2]&&a[n][3])n++,flag=true; // 需要新建一层
                for(int k=1;k<=3;k++){
                    if(a[n][k])continue;
                    a[n][k]=color;
                    minn=min(minn,dfs(gethash())+1.0); // 更新最小期望
                    a[n][k]=0;
                }
                // 将之前修改的状态恢复
                if(flag)n--;
                a[i][j]=color;
            }
        if(minn>1e9)error+=p; // 不存在合法操作
        else sum+=p*minn; // 统计期望
    }
    if(error>0.99)return node[id].p=0; // 游戏结束
    else return node[id].p=(sum+error*1.0)/(1-error); // 统计期望
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            char ch;
            scanf(" %c",&ch);
            if(ch=='R')a[i][j]=1;
            if(ch=='G')a[i][j]=2;
            if(ch=='B')a[i][j]=3;
        }
        if(a[i][1]>a[i][3])swap(a[i][1],a[i][3]); // 等价交换
    }
    printf("%.4lf\n",dfs(gethash()));
    return 0;
}