ZOJ 3329-One Person Game（概率dp，迭代处理环）

题意：

三个色子有k1,2,k3个面每面标号（1-k1,1-k2,1-k3),一次抛三个色子，得正面向上的三个编号，若这三个标号和给定的三个编号a1,b1,c1对应则总和置零，否则总和加上三个色子标号和，直到总和不小于n时结束，求抛色子的期望次数。

分析：

该题状态好分析

dp[i]表示和为i时的期望次数，dp[0]是答案

dp[i]=sum(dp[i+tmp]*p[tmp])+dp[0]*p0+1(tmp是三个色子可得到的标号和);

第一次看到这样的方程不怎么解，看了题解才知道用迭代法，每个dp[i]里都包括dp[0];

令dp[i]=a[i]*dp[0]+b[i],带入上面的方程可得dp[i]=(sum(a[i+tmp]*p[tmp])+p0)*dp[0]+sum(b[i+tmp]*p[tmp])+1;

则a[i]=sum(a[i+tmp]*p[tmp])+p0,b[i]=sum(b[i+tmp]*p[tmp])+1;

则dp[0]=a[0]*dp[0]+b[0],求出答案;

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

double a[],b[],p[];

int n,k1,k2,k3,a1,b1,c1;

void solve(){

    double tp=1.0/(k1*k2*k3);

    memset(p,,sizeof(p));

    memset(a,,sizeof(a));

    memset(b,,sizeof(b));

    for(int i=;i<=k1;++i)

        for(int j=;j<=k2;++j)

        for(int k=;k<=k3;++k)

        if(i!=a1||j!=b1||k!=c1)

        p[i+j+k]+=tp;

    for(int i=n;i>=;--i){

    for(int j=;(i+j)<=n&&j<=k1+k2+k3;++j){

        a[i]+=a[i+j]*p[j];

        b[i]+=b[i+j]*p[j];

      }

    a[i]+=tp;

    b[i]+=1.0;

    }

    printf("%.15lf\n",b[]/(1.0-a[]));

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a1,&b1,&c1);

        solve();

    }

return ;

}

ZOJ 3329-One Person Game（概率dp，迭代处理环）的相关教程结束。