AT_abc184_d 题解

Preface

蒟蒻第一次自己弄出来期望 DP，写篇题解纪念。

Solution

其实和我之前练习到的这道题目很像。

这道题目我们可以记忆化搜索求解。其实递推也可以但是边界可能比记搜难写一些，故这里选择记搜。

看到 A,B,C\leq 99，考虑设 dp_{x,y,z} 表示当前金币、银币、铜币数量分别为 x,y,z 时，操作轮数的期望。下面考虑怎么 DP。

• 终止状态：若当前状态中 x,y,z 中的任意一个 \geq 100，则结束当前记搜。
• 转移方程：
  • 若当前状态 x>0，则 dp_{x,y,z}\leftarrow dp_{x,y,z}+(dp_{x+1,y,z}+1)\times\dfrac{x}{x+y+z}。表示当前选择 x，步数是状态 dp_{x+1,y,z} 再加一步，选择概率是 \dfrac{x}{x+y+z}。
  • 若当前状态 y>0，则 dp_{x,y,z}\leftarrow dp_{x,y,z}+(dp_{x,y+1,z}+1)\times\dfrac{y}{x+y+z}。原理同理。
  • 若当前状态 z>0，则 dp_{x,y,z}\leftarrow dp_{x,y,z}+(dp_{x,y,z+1}+1)\times\dfrac{z}{x+y+z}。原理同理。
• 答案：dp_{A,B,C}。

这道题目就做完了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int a,b,c;
double dp[N][N][N];
double DFS(int x,int y,int z){
    if(x>=100||y>=100||z>=100)return 0;//终止状态 
    if(dp[x][y][z]!=-1)return dp[x][y][z];//记搜的记录 
    double tmp=0;
    //以下是转移 
    if(x)tmp+=(DFS(x+1,y,z)+1.0)*1.0*double(x)/double(x+y+z);
    if(y)tmp+=(DFS(x,y+1,z)+1.0)*1.0*double(y)/double(x+y+z);
    if(z)tmp+=(DFS(x,y,z+1)+1.0)*1.0*double(z)/double(x+y+z);
    return dp[x][y][z]=tmp;
}
signed main(){
    cin>>a>>b>>c;
    for(int i=0;i<=100;i++)
        for(int j=0;j<=100;j++)
            for(int k=0;k<=100;k++)
                dp[i][j][k]=-1;//初始状态 
    printf("%.10lf",DFS(a,b,c));//答案 
    return 0;
}

祝大家 NOIp2024 rp++。