概率dp练习 (16.04.25)

时间：2023-02-13 17:45:52

继续练习之旅，记录3道概率dp的题。希望自己从中收获并成长。

zoj 3822 Domination

http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3822
大意：一天放一个棋子到棋盘中，最后要求每一行每一列至少一个棋子。求解天数期望。
当一个棋子放在一个位置 (i,j)时，所在的行和列均会收到影响。
根据这一点，列出转移方程，设 dp[i][j][k] ，表示用k个棋子控制i行j列的棋盘所用到的概率。
那么有：

dp[i][j][k+1]=dp[i][j][k]×i×j−kn×m−k    已控制i行j列dp[i][j+1][k+1]=dp[i][j][k]×i×(m−j)n×m−k    已控制行dp[i+1][j][k+1]=dp[i][j][k]×(n−i)×jn×m−k    已控制列dp[i+1][j+1][k+1]=dp[i][j][k]×(n−i)×(m−j)n×m−k    未控制

求期望，我们往往将其转化成从后向前推。
于是我们得到：
dp[i][j][k]=dp[i][j][k+1]×i×j−kn×m−k+dp[i][j+1][k+1]i×(m−j)n×m−k+dp[i+1][j][k+1](n−i)×jn×m−k+dp[i+1][j+1][k+1]×(n−i)×(m−j)n×m−k+1

从后向前推可以得到好处：对于求解 “>=n” 类问题的最后结果即是dp[0]。例如本题，从前向后推的话答案应该是 ∑kn∗mdp[n][m][k] 。但如果是从后前向推导，结果就是 dp[0][0][0] 。 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2505;
double dp[55][55][N];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        double ans=0;
        int len=n*m,i,j,k;
        for(i=n;i>=0;i--){
            for(j=m;j>=0;j--){
                if(i==n && j==m)  continue;
                int minm=max(i,j);
                for(k=i*j;k>=minm;k--){
                    dp[i][j][k]=1;
                    dp[i][j][k]+=dp[i][j][k+1]*(1.0*i*j-k)/(len-k);
                    dp[i][j][k]+=dp[i][j+1][k+1]*1.0*i*(m-j)/(len-k);
                    dp[i][j][k]+=dp[i+1][j][k+1]*1.0*(n-i)*j/(len-k);
                    dp[i][j][k]+=dp[i+1][j+1][k+1]*1.0*(n-i)*(m-j)/(len-k);
                }
            }
        }
        printf("%.12lf\n",dp[0][0][0]);
    }
    return 0;
}

poj 3071 Football

http://poj.org/problem?id=3071
大意： 2n 支队伍进行淘汰赛，问谁的获胜几率最大。各队伍对其他队伍的胜利几率以矩阵的形式给出。
分析：咋一看好家伙，本题有随机性，递归性，局部性。
关键要素：比赛轮数，队伍。
设dp[i][j]是第i轮比赛中队伍j获胜的概率。那么有递推式: dp[i][j]=∑dp[i−1][j]×p[j][k]×dp[i−1][k] .
怎样把i轮比赛中的各队伍分开进行局部比赛？小技巧，神奇的二进制，从0开始，相邻的队伍排名相差不超过1。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
double mat[1300][1300];
double dp[100][1300];
const double eps=1e-6;
int main()
{
    int n;
    while(cin>>n){
        if(n==-1) break;
        memset(dp,0,sizeof(dp)); //初始化！！！
        int L=1<<n; // 队伍总个数
        for(int i=0;i<L;i++){
            for(int j=0;j<L;j++){
                scanf("%lf",&mat[i][j]);
            }
        }
        int ans=0;
        for(int i=0;i<L;i++) dp[0][i]=1;  //最开始大家都存在
        for(int i=1;i<=n;i++){
            for(int j=0;j<L;j++){
                for(int k=0;k<L;k++){
                    int p1=j>>(i-1), p2=k>>(i-1);   //神奇的二进制，分开了各轮
                    if(p1&1){
                        if(p1-1==p2){  // 奇减偶加比较相邻
                            dp[i][j]+=dp[i-1][j]*mat[j][k]*dp[i-1][k];
                        }
                    }
                    else {
                        if(p1+1==p2){
                            dp[i][j]+=dp[i-1][j]*mat[j][k]*dp[i-1][k];
                        }
                    }
                }
            }
        }
        for(int i=0;i<L;i++){
            if(dp[n][i]-dp[n][ans]>eps) ans=i;
            //cout<<i+1<<": "<<dp[n][i]<<endl;
        }
        printf("%d\n",ans+1);
    }
    return 0;
}
/* 0: 0000 1: 0001 2: 0010 3: 0011 4: 0100 5: 0101 6: 0110 7: 0111 */

zoj 3329 one person gam

http://www.icpc.moe/onlinejudge/showProblem.do?problemCode=3329
大意：一次掷3个色子，如果3个色子的点数分别是a, b, c，那么计数变成0，否则计数器加上3个点数之和。求解点数超过n的掷色子次数期望。

dp[i]=∑dp[i+k]pk+dp[0]p0+1设置：  dp[i]=a[i]dp[0]+b[i]−−>dp[i]=∑(a[i+k]dp[0]+b[i+k])pk+dp[0]p0+1=dp[0](∑a[i+k]pk+p0)+∑b[i+k]pk+1−−>a[i]=∑a[i+k]pk+p0b[i]=∑b[i+k]pk+1dp[0]=a[0]dp[0]+b[0]−−>dp[0]=b[0]1−a[0] 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
double a[510],b[510];
int main()
{
    //freopen("cin.txt","r",stdin);
    int t;
    cin>>t;
    while(t--){
        int n,k1,k2,k3,A,B,C;
        scanf("%d %d %d %d %d %d %d",&n,&k1,&k2,&k3,&A,&B,&C);

        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));

        double p0=1.0/k1/k2/k3;
        for(int it=n;it>=0;it--){
            for(int i=k1;i>=1;i--){
                for(int j=k2;j>=1;j--){
                    for(int k=k3;k>=1;k--){
                        if(i==A && j==B && k==C)  {
                             continue;
                        }
                        a[it]+=a[it+i+j+k]*p0;
                        b[it]+=b[it+i+j+k]*p0;
                    }
                }
            }
            a[it]+=p0;
            b[it]++;
        }
        printf("%.15lf\n",b[0]/(1-a[0]));
    }
    return 0;
}
标签：

相关文章