题解与代码 - Colored Jenga

## 状态压缩动态规划

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

**结论 1：有效层总数不会超过 $n+1$。**

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

**结论 2：任意两层非顶层的有效层，可以任意交换。**（这是显然的）

**结论 3：任意一层有效层的左右两个位置对称，可以交换。**（这也是显然的）

考虑状态压缩。

对于一个塔的状态，每一层一个位置有四种状态：放置了木板（三种颜色），以及没有放置木板。而每一层有三个位置，需要占用 $6$ 个二进制位。对于一个塔的状态，有效层至多 $n+1\leq 7$ 层，即至多占用 $6\times 7=42$ 个二进制位，只需使用 `unsigned long long` 存储即可。

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

具体细节见代码实现。

```cpp
// 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;
}

```

Colored Jenga

状态压缩动态规划

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

结论 1：有效层总数不会超过 $n+1$ 。

结论 2：任意两层非顶层的有效层，可以任意交换。（这是显然的）

结论 3：任意一层有效层的左右两个位置对称，可以交换。（这也是显然的）

考虑状态压缩。

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

具体细节见代码实现。

代码

// 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;
}