文章目錄

• • 概念：
• 例題
• • 引入：
  • • 解答：
  • Happy Running NC15532
  • • 題意：
    • 題解：
    • 代碼：
  • poj2096 NC106693 Collecting Bugs
  • • 題意：
    • 題解：
    • 代碼：
  • NC210477 帶富翁
  • • 題意：
    • 題解：
    • 代碼：
  • NC210481 篩子游戲
  • • 題意：
    • 題解：
    • 代碼：
  • NC210487 食堂
  • • 題意：
    • 題解：
    • 代碼：
• 習(xí)題
• • CF148D Bag of mice
  • CF16E Fish
  • CF235B Let's Play Osu!
  • NC14378 珂學(xué)送分
  • NC20263 [SCOI2008] 獎(jiǎng)勵(lì)關(guān)
  • NC20709 Balls
  • NC210515 迷宮游戲
  • NC210516 抽卡

概念：

概率
期望：數(shù)學(xué)期望(mean)（或均值，亦簡(jiǎn)稱期望）是試驗(yàn)中每次可能結(jié)果的概率乘以其結(jié)果的總和，是最基本的數(shù)學(xué)特征之一。它反映隨機(jī)變量平均取值的大小。

例題

引入：

甲乙兩個(gè)人賭博，他們兩人獲勝的機(jī)率相等，比賽規(guī)則是先勝三局者為贏家，贏家可以獲得
100法郎的獎(jiǎng)勵(lì)。當(dāng)比賽進(jìn)行到第四局的時(shí)候，甲勝了兩局，乙勝了一局，這時(shí)由于某些原
因中止了比賽，那么如何分配這100法郎才比較公平？

解答：

乙獲勝概率是1/4，甲是3/4，所以按照這個(gè)分錢(qián)

Happy Running NC15532

題意：

小明需要在操場(chǎng)順時(shí)針跑圈打卡，操場(chǎng)上有兩個(gè)打卡點(diǎn)A，B， 他需要先在A點(diǎn)打卡，然后在B點(diǎn)打卡（哪怕B點(diǎn)在A點(diǎn)前面），打完卡就可以結(jié)束跑步了，他的起點(diǎn)以及A，B兩點(diǎn)的位置是隨機(jī)的，告訴你操場(chǎng)的長(zhǎng)度X米，求他需要跑超過(guò)K米的概率。
先輸入K，再輸入X
輸入：

3 2 2 4 3 2 1

? 輸出：

0.50 0.22 0.00

題解：

固定起點(diǎn)，分類討論
情況1：
當(dāng)A在B前：此時(shí)所跑距離小于等于一圈
列出相關(guān)式子：
K < X
A < B
B > = K
A < = x
B < = x
概率為圖中陰影部分占整個(gè)正方形
即

情況2：
A在B后：

情況3：
K == X時(shí)，(其實(shí)是求B在A前的概率)也就是0.5

代碼：

poj2096 NC106693 Collecting Bugs

題意：

題意：
一個(gè)軟件有s個(gè)子系統(tǒng)，會(huì)產(chǎn)生n種bug。
某人一天發(fā)現(xiàn)一個(gè)bug，這個(gè)bug屬于某種bug，發(fā)生在某個(gè)子系統(tǒng)中。
求找到所有的n種bug，且每個(gè)子系統(tǒng)都找到bug，這樣所要的天數(shù)的期望。
需要注意的是：bug的數(shù)量是無(wú)窮大的，所以發(fā)現(xiàn)一個(gè)bug，出現(xiàn)在某個(gè)子系統(tǒng)的概率是1/s，
屬于某種類型的概率是1/n。
? (0 < n, s <= 1 000)
? 輸入：
? 1 2
? 輸出：
? 3.00000

題解：

? f[i][j]表示現(xiàn)在已經(jīng)找到的bug有i種，屬于j個(gè)系統(tǒng)，找完剩下所需bug的期望天數(shù)。
? 已知：f[n][s]=0，因?yàn)橐呀?jīng)達(dá)到目標(biāo)， 而要求的答案是f[0][0]
dp[i][j]狀態(tài)可以轉(zhuǎn)化成以下四種：
dp[i][j] 發(fā)現(xiàn)一個(gè)bug屬于已經(jīng)找到的i種bug和j個(gè)子系統(tǒng)中
dp[i+1][j] 發(fā)現(xiàn)一個(gè)bug屬于新的一種bug，但屬于已經(jīng)找到的j種子系統(tǒng)
dp[i][j+1] 發(fā)現(xiàn)一個(gè)bug屬于已經(jīng)找到的i種bug，但屬于新的子系統(tǒng)
dp[i+1][j+1]發(fā)現(xiàn)一個(gè)bug屬于新的一種bug和新的一個(gè)子系統(tǒng)
以上四種的概率分別為：
p1 = i * j / (n * s)
p2 = (n-i) * j / (n * s)
p3 = i * (s-j) / (n * s)
p4 = (n-i)* (s-j) / (n * s)
又因?yàn)镋(aA+bB+…) = aE(A) + bE(B)
所以dp[i,j] = p1 * dp[i,j] + p2 * dp[i+1,j] + p3 * dp[i,j+1] + p4 * dp[i+1,j+1] + 1;
dp[i,j] = ( 1 + p2 * dp[i+1,j] + p3* dp[i,j+1] + p4 * dp[i+1,j+1] )/( 1-p1 )
= ( n * s + (n-i) * j * dp[i+1,j] + i*(s-j) * dp[i,j+1] + (n-i) * (s-j) * dp[i+1 , j+1] )/( n * s - i * j )

代碼：

#include<iostream> #include<cstdio> #include<cstring>using namespace std;const int N=1010;double dp[N][N];int main(){//freopen("input.txt","r",stdin);int n,s;while(~scanf("%d%d",&n,&s)){dp[n][s]=0;for(int i=n;i>=0;i--)for(int j=s;j>=0;j--){if(i==n && j==s)continue;dp[i][j]=(i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)/(n*s-i*j);}printf("%.4f\n",dp[0][0]);}return 0; }

NC210477 帶富翁

題意：

? 小明在玩一款帶富翁游戲，這個(gè)游戲具體來(lái)說(shuō)就是有n個(gè)獎(jiǎng)勵(lì)點(diǎn)，每個(gè)獎(jiǎng)勵(lì)點(diǎn)有一定的獎(jiǎng)勵(lì)分。
一開(kāi)始他站在位置1。每次他都會(huì)扔一個(gè)有6面的篩子，如果扔到了x，并且小明現(xiàn)在站在i這個(gè)位置，小明就會(huì)向前進(jìn)x步到達(dá)i+x這個(gè)位置。
? 如果小明扔出了x并且i+x已經(jīng)大于了n，那么小明就會(huì)重新扔，直到i+x在合適的位置。小明
最后如果到達(dá)了n號(hào)位置，那么小明就會(huì)結(jié)束游戲，現(xiàn)在小明想知道自己期望的得分是多少。

題解：

? f[i]表示從i走到n獲得的金子的期望，
? i+6 <= n 即不會(huì)走出去：f[i] = a[i] + ∑(1/6 * f[j]) ( i+1<=j<=i+6)
? i+6>n f[i] = (f[i + 1] + … + f[n]) / (n - i)。

代碼：

NC210481 篩子游戲

題意：

? 吉吉國(guó)王正在玩一款手游，這個(gè)手游的規(guī)則非常簡(jiǎn)單。一開(kāi)始你會(huì)得到三個(gè)篩子，三個(gè)篩子分別有k1,k2,k3面，也就是說(shuō)分別可以扔出[1,k1],[1,k2],[1,k3]之間數(shù)。
? 一開(kāi)始的分?jǐn)?shù)為0，每次扔篩子都會(huì)扔出x,y,z三個(gè)數(shù)，但是這個(gè)游戲的特別之處在于每次開(kāi)
局都會(huì)給定三個(gè)數(shù)a,b,c，如果滿足x=a,y=b,z=c，那么你的分?jǐn)?shù)就會(huì)清零，否則你的分?jǐn)?shù)就會(huì)加上x(chóng)+y+z。現(xiàn)在吉吉國(guó)王想知道需要扔多少次才能使得他的分?jǐn)?shù)大于n。 ? 0≤n≤500

題解：

? 設(shè)f[i]表示達(dá)到i分時(shí)到達(dá)目標(biāo)狀態(tài)的期望，pk為投擲k分的概率，p0為回到0的概率，這個(gè)先預(yù)處理出來(lái)
? 則f[i]=∑(pk * f[i+k])+f[0 ] * p0+1
? f[i]=∑(pk * f[i+k])+f[0] * p0+1
? 每個(gè)狀態(tài)都和f[0]有關(guān)系，而且f[0]就是我們所求，為一個(gè)常數(shù)
? 設(shè)f[i]=A[i] * f[0]+B[i];
? 代入上述方程右邊得到：
? f[i]=∑(pk * A[i+k] * f[0]+pk * B[i+k])+f[0] * p0+1=
? (∑(pk* A[i+k])+p0)f[0]+∑(pk * B[i+k])+1;
? 所以 A[i]=(∑(pk* A[i+k])+p0) B[i]=∑(pk * B[i+k])+1
? 先遞推求得A[0]和B[0] 那么 f[0]=B[0]/(1-A[0]);

代碼：

NC210487 食堂

題意：

? 1≤k≤m≤n≤2000

題解：

? 設(shè)f[i][j]表示i個(gè)人排隊(duì),Tomato排在第j個(gè)位置，達(dá)到目標(biāo)狀態(tài)的概率(j<=i)
? f[n][m]就是所求
? j==1: f[i][1]=p1 * f[i][1]+p2 * f[i][i]+p4;
? 2<=j<=k: f[i][j]=p1 * f[i][j]+p2 * f[i][j-1]+p3 * f[i-1][j-1]+p4;
? k<j<=i: f[i][j]=p1 * f[i][j]+p2 * f [i][j-1]+p3 * f [i-1][j-1];

代碼：

習(xí)題

CF148D Bag of mice

CF16E Fish

CF235B Let’s Play Osu!

NC14378 珂學(xué)送分

NC20263 [SCOI2008] 獎(jiǎng)勵(lì)關(guān)

NC20709 Balls

NC210515 迷宮游戲

NC210516 抽卡

總結(jié)

以上是生活随笔為你收集整理的牛客网专题 概率dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。