[数据结构与算法]Codeforces 1543 C. Need for Pink Slips —— 暴力dfs

This way

题意：

一开始有三个选项，每个选项都有一个概率，它们概率之和为1.每次等概率选择一个选项，选到p的时候结束回合。否则假设当前选项的概率为a。
如果a<=v，那么将这个选项的值减为0并且抹除，将a等份分给剩下的选项。
如果a>v，那么将这个选项的值减v，将v等份分给剩下的选项。
问你期望几步结束游戏。

题解：

我一眼感觉是动态规划，但是这个好像不好做。然后发现v的数据范围是>=0.1哦，那么每次p至少增加0.5，也就是说最多20步结束游戏。然后每次如果要游戏继续下去的话只有两个选项，也就是所有情况差不多是$2^{20}$，乘上t之后也就是1e7的时间复杂度。
可以记录步数直接计算期望，也可以在回溯的时候计算，ans+=p*(1+dfs())的意思是如果选择了这一步，那么概率就是p，因为这一步一定要走，所以它的期望步数就是p1，pdfs()表示这一步后面的期望步数要乘上这一步的概率，两者相加就是这一步的贡献

#include<bits/stdc++.h>
using namespace std;
#define ld long double
const ld eps=1e-9;
const int N=1e6+5;
ld v;
int dcmp(ld a,ld b){
    if(a-b<eps)return -1;
    if(a-b>eps)return 1;
    return 0;
}
ld dfs(ld c,ld m,ld p){
    ld ans=p;
    if(c!=0){
            //cout<<c<<" "<<dcmp(c,0.0)<<endl;
        if(dcmp(c,v)==1){
            if(m!=0)
                ans+=c*(1+dfs(c-v,m+v/2,p+v/2));
            else
                ans+=c*(1+dfs(c-v,0,p+v));
        }
        else{
            if(m!=0)
                ans+=c*(1+dfs(0,m+c/2,p+c/2));
            else
                ans+=c*(1+dfs(0,0,p+c));
        }
    }
    if(m!=0){
        if(dcmp(m,v)==1){
            if(c!=0)
                ans+=m*(1+dfs(c+v/2,m-v,p+v/2));
            else
                ans+=m*(1+dfs(0,m-v,p+v));
        }
        else{
            if(c!=0)
                ans+=m*(1+dfs(c+m/2,0,p+m/2));
            else
                ans+=m*(1+dfs(0,0,p+m));
        }
    }
    return ans;
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        ld c,m,p;
        cin>>c>>m>>p>>v;
        cout<<fixed<<setprecision(10)<<dfs(c,m,p)<<endl;
    }
    return 0;
}