牛客-篩子游戲 (概率dp)

題目鏈接

題解：
設 d p [ i ] dp[i] dp[i] 表示當前分數為 i i i 要達到目標的期望，則：

d p [ i ] = ∑ k = 3 k 1 + k 2 + k 3 ( p [ k ] ? d p [ i + k ] ) + p [ 0 ] ? d p [ 0 ] + 1 dp[i]=\sum_{k=3}^{k1+k2+k3} (p[k] \cdot dp[i+k])+ p[0] \cdot dp[0] +1 dp[i]=∑k=3k1+k2+k3?(p[k]?dp[i+k])+p[0]?dp[0]+1,接下來的構造非常的妙，

設 d p [ i ] = a [ i ] ? d p [ 0 ] + b [ i ] dp[i]=a[i] \cdot dp[0]+b[i] dp[i]=a[i]?dp[0]+b[i]，那么式子可以變成：

d p [ i ] = ∑ k = 3 k 1 + k 2 + k 3 ( p [ k ] ? a [ i + k ] ? d p [ 0 ] + p [ k ] ? b [ i + k ] ) + p [ 0 ] ? d p [ 0 ] + 1 dp[i]=\sum_{k=3}^{k1+k2+k3}(p[k] \cdot a[i+k] \cdot dp[0] +p[k] \cdot b[i+k]) +p[0] \cdot dp[0]+1 dp[i]=∑k=3k1+k2+k3?(p[k]?a[i+k]?dp[0]+p[k]?b[i+k])+p[0]?dp[0]+1

那么可以推出： a [ i ] = ∑ k = 3 k 1 + k 2 + k 3 ( p [ k ] ? a [ i + k ] ) + d p [ 0 ] a[i]=\sum_{k=3}^{k1+k2+k3} (p[k] \cdot a[i+k])+dp[0] a[i]=∑k=3k1+k2+k3?(p[k]?a[i+k])+dp[0], b [ i ] = ∑ k = 3 k 1 + k 2 + k 3 ( p [ k ] ? b [ i + k ] ) + 1 b[i]=\sum_{k=3}^{k1+k2+k3} (p[k] \cdot b[i+k])+1 b[i]=∑k=3k1+k2+k3?(p[k]?b[i+k])+1

根據遞推式，就可以從后往前求出 a [ 0 ] a[0] a[0] 和 b [ 0 ] b[0] b[0] , d p [ 0 ] = b [ 0 ] / ( 1 ? a [ 0 ] ) dp[0]=b[0]/(1-a[0]) dp[0]=b[0]/(1?a[0])

代碼

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int>pii;
const int MAXN=5e2+500;
const int mod=1004535809;
const int inf=0x3f3f3f3f;
double p[MAXN];
double aa[MAXN];
double bb[MAXN];
int main()
{
    int n,k1,k2,k3,a,b,c;
    cin>>n>>k1>>k2>>k3>>a>>b>>c;
    p[0]=1.0/(k1*k2*k3);
    for(int i=3;i<=k1+k2+k3;i++)
    {
        int cnt=0;
        for(int t1=1;t1<=k1;t1++)
        {
            for(int t2=1;t2<=k2;t2++)
            {
                for(int t3=1;t3<=k3;t3++)
                {
                    if(t1==a&&t2==b&&t3==c) continue;
                    if(t1+t2+t3==i) cnt++;
                }
            }
        }
        p[i]=1.0*cnt/(k1*k2*k3);
    }
    for(int i=n;i>=0;i--)
    {
        for(int k=3;k<=k1+k2+k3;k++)
        {
            aa[i]+=aa[i+k]*p[k];
            bb[i]+=p[k]*bb[i+k];
        }
        aa[i]+=p[0];
        bb[i]+=1.0;
    }
    double ans=bb[0]/(1-aa[0]);
    printf("%.8lf\n",ans);
}