ZOJ 3329 【概率DP】

题意:

给你三个均匀k面筛子。

分别有k1 k2 k3个面,每个面朝上的概率是相等的。

如果第一个筛子出现a第二个筛子出现b第三个筛子出现c那么置零。

否则在当前和加上三个点数之和。

求当前和大于n需要的步数的期望。

思路:

一开始状态转移搞错了,手推公式交了WA,后来想了想状态转移的过程发现每个状态都跟0状态有关系,但是dp[0]不确定,但是幸运的是这是一个线性变换,所以状态转移的时候记录一下dp[0]的系数,最后移项输出就好了。

dp[i]=dp[i+x]*(k1*k2*k3);(x=i+j+k)(i=1...k1  j=1...k2  k=1...k3)

错误:

总的状态数量一开始脑残写成了k1+k2+k3

shit

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
double dp1[1000],dp2[1000];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,aa,bb,cc,a,b,c;
        scanf("%d%d%d%d%d%d%d",&n,&aa,&bb,&cc,&a,&b,&c);
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        for(int w=n; w>=0; w--)
        {
            for(int i=1; i<=aa; i++)
            {
                for(int j=1; j<=bb; j++)
                {
                    for(int k=1; k<=cc; k++)
                    {
                        if(i==a&&j==b&&k==c)
                        {
                            dp2[w]+=1.0/(aa*bb*cc);
                        }
                        else
                        {
                            dp2[w]+=dp2[w+i+j+k]/(aa*bb*cc);
                            dp1[w]+=dp1[w+i+j+k]/(aa*bb*cc);
                        }
                    }
                }
            }
            dp1[w]+=1;
        }
        printf("%.15lf\n",dp1[0]/(1-dp2[0]));
    }
}
时间: 12-18

ZOJ 3329 【概率DP】的相关文章

zoj 3329 概率dp

看了这么多,也就是个递推 1 /* 2 ZOJ 3329 3 题意:有三个骰子,分别有k1,k2,k3个面. 4 每次掷骰子,如果三个面分别为a,b,c则分数置0,否则加上三个骰子的分数之和. 5 当分数大于n时结束.求游戏的期望步数.初始分数为0 6 7 设dp[i]表示达到i分时到达目标状态的期望,pk为投掷k分的概率,p0为回到0的概率 8 则dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1; 9 都和dp[0]有关系,而且dp[0]就是我们所求,为常数 10 设dp[i]=A

zoj 3822概率dp

Domination Time Limit: 8 Seconds Memory Limit: 131072 KB Special Judge Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboard with N r

zoj 3822 概率dp

1 /* 2 题目大意:一个n*m的棋盘,每天放一个棋子,每行每列至少有一个棋子时结束.求达到每行每列至少有一个棋子的天数的数学期望. 3 */ 4 #include <iostream> 5 #include <cstdio> 6 #include <cstring> 7 using namespace std; 8 9 const int maxn=55; 10 double dp[maxn*maxn][maxn][maxn];//放i颗棋子,j行有棋子,k列有棋子

ZOJ 3329 期望DP

题目大意: 给定3个已经规定好k1,k2,k3面的3个色子,如果扔到a,b,c则重新开始从1 计数,否则不断叠加所有面的数字之和,直到超过n,输出丢的次数的数学期望 我们在此令dp[]数组记录从当前数值到结束的数学期望 假如有3个面数都为2的色子 那么dp[i] = 1.0 / 2/2/2 * dp[0] + 1.0/8*dp[i+3] +3.0/8*dp[i+4]+3.0/8*dp[i+5]+1.0/8*dp[i+6] + 1 当然那些下标大于i的dp值均为0 可是我们这样从后往前推会导致无法

zoj 3735 概率dp

Josephina and RPG Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge A role-playing game (RPG and sometimes roleplaying game) is a game in which players assume the roles of characters in a fictional setting. Players take responsibil

ZOJ 3551 Bloodsucker (概率DP)

ZOJ Problem Set - 3551 Bloodsucker Time Limit: 2 Seconds      Memory Limit: 65536 KB In 0th day, there are n-1 people and 1 bloodsucker. Every day, two and only two of them meet. Nothing will happen if they are of the same species, that is, a people

【概率DP】 ZOJ 3380 Patchouli&#39;s Spell Cards

通道 题意:有m个位置,每个位置填入一个数,数的范围是1~n,问至少有L个位置的数一样的概率 思路: 总数是n^m,我们求没有L个位置一样的数的概率 * 设 dp[i][j]表示用前i个数,填充j个位置的方案数(要符合没有L个位置是一样的数) * dp[i][j]=dp[i-1][j]+Sigm( dp[i-1][j-k]*C[m-(j-k)][k] ) k<=j&&k<L * 其实就是看第i个数,可以不填,填一个位置,两个位置······这样累加过来. * 那么最后的答案就是

[概率dp] zoj 3822 Domination

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3822 Domination Time Limit: 8 Seconds      Memory Limit: 131072 KB      Special Judge Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays che

zoj 3822 Domination 【概率DP 求期望】

Domination Time Limit: 8 Seconds      Memory Limit: 131072 KB      Special Judge Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboar

zoj 3288 Domination (概率dp)

///dp[i][j][k]表示i行j列已经有棋子,且放了k个的概率 ///dp[i][j][k]一共有四种转移方式 ///1:dp[i-1][j][k-1] 概率为 (n-(i-1))*j/(n*m-(k-1)) ///2:dp[i][j-1][k-1] 概率为 i*(m-(j-1))/(n*m-(k-1)) ///3:dp[i-1][j-1][k-1] 概率为 (n-(i-1))*(m-(j-1))/(n*m-(k-1)) ///4:dp[i][j][k-1] 概率为 (i*j-(k-1))