题解 AT4531 Sushi

· · 题解

AT4531 Sushi

题目传送门

更好的阅读体验

暴力dp

首先我们考虑最暴力的做法，用dp[a_1][a_2]···[a_n]表示第i盘还剩a_i个寿司的期望次数。那么枚举随机到的数i就可以得到方程：

dp[a_1][a_2]···[a_n]=1+\sum_{i=1}^{n} \frac{1}{n}dp[a_1][a_2]···[\max(a_i-1,0)]···[a_n]

合并状态

（注意该方程并不能构成转移方程，因为当第i盘已经为空的时候，状态不变）我们现在考虑合并等价状态（题外话：动态规划优化的初等方法无非就那么几种，合并状态就是最重要的思想之一）。

注意到由于随机数是均匀选取的，那么盘子的位置是无关紧要的，而只有剩 余数量有影响。于是相同数值的不同排列的期望次数必然是相同的。例如dp[1][2][3]=dp[3][2][1]。

所以只需要考虑每种数值出现的次数。因为a_i \le 3，所以至多有四种不同数值：{0,1,2,3}。我们重新定义状态dp[a][b][c][d]表示当前还剩下 a/b/c/d盘有0/1/2/3个寿司。

有了状态，我们通过枚举当前随机到的盘子里还剩几只寿司得到如下方程：

dp[a][b][c][d]=1+\frac{a}{n}dp[a][b][c][d]+\frac{b}{n}dp[a+1][b-1][c][d]+\frac{c}{n}dp[a][b+1][c-1][d]+\frac{d}{n}dp[a][b][c+1][d-1]

移项整理得到转移方程：

dp[a][b][c][d]=\frac{n}{b+c+d}+\frac{b}{b+c+d}dp[a+1][b-1][c][d]+\frac{c}{b+c+d}dp[a][b+1][c-1][d]+\frac{d}{b+c+d}dp[a][b][c+1][d-1]

消除无用状态

但由于n \le 300，总状态数高达300^{4} \approx 8×10^{9}无法通过。我们需要进一步优化。

注意到任意时刻下，a + b + c + d的值都应该等于n：因为不管进行多少次操作，盘子总数总是n。所以其实只需要知道b,c,d就可以反推出a的值：a = n−(b + c + d)。那么现在只保留后面三维，得到转移方程：

dp[b][c][d]=\frac{n}{b+c+d}+\frac{b}{b+c+d}dp[b-1][c][d]+\frac{c}{b+c+d}dp[b+1][c-1][d]+\frac{d}{b+c+d}dp[b][c+1][d-1]

本题参考程序如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int maxm=1e6+5;
double f[305][305][305];
int a[5],n; 
int main(int argc,char const *argv[]){
    scanf("%d",&n);
    for(int i=1,x;i<=n;++i){
        scanf("%d",&x);
        a[x]++;
    }   
    for(int k=0;k<=n;++k){
        for(int j=0;j<=n;++j){
            for(int i=0;i<=n;++i){
                if(i||j||k){
                    if(i)f[i][j][k]+=f[i-1][j][k]*i/(i+j+k);
                    if(j)f[i][j][k]+=f[i+1][j-1][k]*j/(i+j+k);
                    if(k)f[i][j][k]+=f[i][j+1][k-1]*k/(i+j+k);
                    f[i][j][k]+=(double)n/(i+j+k);
                }
            }
        }
    }
    printf("%.15lf\n",f[a[1]][a[2]][a[3]]);
    return 0;
}

本篇题解就到此结束了，如果喜欢，还请点个赞吧。