筛子游戏（概率DP） 牛客

题目在这里

题目大意: 有三个面数给定的骰子，每次投出前进x+y+z(三个骰子投出的数字),开始位置在0点,问位置>n的期望步数？ 特别的,如果x==a&&y==b&&z==c会回到0点

分析： 设f[i]表示分数到达i的期望步数 $f[i]=\sum (pk\ast f[i+k])+p0\ast f[0]+1$ 但是f[0]是一个未知数，所以需要使用一种常见手法进行转化。 设 $f[i]=A[i]\ast f[0]+B[i]$ 带入方程右边 $f[i]=\sum (pk\ast A[i+k]\ast f[0]+pk\ast B[i+k])+p0\ast f[0]+1$ $=(\sum (pk\ast A[i+k])+p0)\ast f0+\sum (pk\ast B[i+k])+1$ 得到 $A[i]=\sum (pk\ast A[i+k])+p0$ $B[i]=\sum (pk\ast B[i+k])+1$

已知： $A[n]=0$ $B[n]=0$

可以递推求解A[0]和B[0] 最后得到f[0]

$f[0]=B[0]/(1-A[0])$

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

double n,a,b,c,k1,k2,k3,p0;
double p[1024],A[1024],B[1024];

int main(){
    ios;
    cin>>n>>k1>>k2>>k3>>a>>b>>c;
    p0 = 1.0/k1/k2/k3;
    for(int i = n;i>=0;--i){
        for(int x = 1;x<=k1;++x){
            for(int y = 1;y<=k2;++y){
                for(int z = 1;z<=k3;++z){
                    if(x==a&&y==b&&z==c) continue;
                    int k = x+y+z;
                    A[i] += p0*A[i+k];
                    B[i] += p0*B[i+k];
                }
            }
        }
        A[i]+=p0;
        B[i]+=1.0;
    }
    double ans = B[0]/(1.0-A[0]);
    cout<<fixed<<setprecision(10)<<ans<<'\n';
    return 0;
}

好想学会DP