概率 d p dp dp習題

前言：太菜了，沒學這個知識點，來補了，希望不咕咕咕，

1.D. Bag of mice

思路：板子題，求公主贏的概率，狀態設為 d p [ i ] [ j ] dp[i][j] dp[i][j]有 i i i只白鼠， j j j只黑鼠，公主先手贏得概率，
首先初始化： d p [ i ] [ 0 ] = 1 , d p [ 0 ] [ j ] = 0 , i ∈ [ 1 , w ] , j ∈ [ 0 , b ] dp[i][0]=1,dp[0][j]=0,i\in[1,w],j\in[0,b] dp[i][0]=1,dp[0][j]=0,i∈[1,w],j∈[0,b]
然后狀態轉移：
分四種情況：
1.公主摸到白鼠， d p [ i ] [ j ] + = i i + j dp[i][j]+=\dfrac{i}{i+j} dp[i][j]+=i+ji?
2.公主摸到黑鼠,龍摸到白鼠，直接輸了，不用加，
3.公主摸到黑鼠，龍摸到黑鼠，且跑出一個黑鼠，
d p [ i ] [ j ] + = j i + j × j ? 1 i + j ? 1 × j ? 2 i + j ? 2 × d p [ i ] [ j ? 3 ] dp[i][j]+=\dfrac{j}{i+j}\times \dfrac{j-1}{i+j-1} \times \dfrac{j-2}{i+j-2}\times dp[i][j-3] dp[i][j]+=i+jj?×i+j?1j?1?×i+j?2j?2?×dp[i][j?3]
4.公主摸到黑鼠，龍摸到黑鼠，且跑出一個白鼠，
d p [ i ] [ j ] + = j i + j × j ? 1 i + j ? 1 × i i + j ? 2 × d p [ i ? 1 ] [ j ? 2 ] dp[i][j]+=\dfrac{j}{i+j}\times \dfrac{j-1}{i+j-1} \times \dfrac{i}{i+j-2}\times dp[i-1][j-2] dp[i][j]+=i+jj?×i+j?1j?1?×i+j?2i?×dp[i?1][j?2]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int w,b;
double dp[N][N]; 
int main(){
	scanf("%d%d",&w,&b);
	for(int i=0;i<=w;i++) dp[i][0]=1;
	for(int i=0;i<=b;i++) dp[0][i]=0;
	for(int i=1;i<=w;i++)
		for(int j=1;j<=b;j++){
			dp[i][j]+=(double)i/(i+j);
			if(j>=3){
				dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2)*dp[i][j-3];
			}
			if(j>=2){
				dp[i][j]+=(double)j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2)*dp[i-1][j-2]; 
			}
		}
	printf("%.9f\n",dp[w][b]);
	return 0;
}

2.ICPC模擬賽 D.Pokemon Ultra Sun

題意：兩個寶可夢初始血量為 h p 1 , h p 2 hp_1,hp_2 hp1?,hp2?，第一個寶可夢每回合有 p p p的概率對第二個寶可夢造成 w w w傷害，有 ( 1 ? p ) (1-p) (1?p)的概率對自己造成 w w w傷害，求回合數的期望，
思路：令 d p [ i ] [ j ] dp[i][j] dp[i][j]表示第一個寶可夢血量為 i i i，第二個寶可夢血量為 j j j的回合數期望，
狀態轉移方程：
d p [ i ] [ j ] = p × ( d p [ i ] [ m a x ( 0 , j ? w ) ] + 1 ) + ( 1 ? p ) × ( d p [ m a x ( 0 , i ? w ) ] [ j ] + 1 ) = 1 + p × d p [ i ] [ m a x ( 0 , j ? w ) ] + ( 1 ? p ) × d p [ m a x ( 0 , i ? w ) ] [ j ] dp[i][j]\\=p\times (dp[i][max(0,j-w)]+1)+(1-p)\times (dp[max(0,i-w)][j]+1) \\=1+p\times dp[i][max(0,j-w)]+(1-p)\times dp[max(0,i-w)][j] dp[i][j]=p×(dp[i][max(0,j?w)]+1)+(1?p)×(dp[max(0,i?w)][j]+1)=1+p×dp[i][max(0,j?w)]+(1?p)×dp[max(0,i?w)][j]

初始狀態： d p [ 0 ] [ 0 ] = d p [ i ] [ 0 ] = d p [ 0 ] [ i ] = 0 dp[0][0]=dp[i][0]=dp[0][i]=0 dp[0][0]=dp[i][0]=dp[0][i]=0，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int T,h1,h2,w;
double p;
double dp[N][N];
int main(){
    cin>>T;
    while(T--){
        cin>>h1>>h2>>w>>p;mst(dp,0);
        for(int i=1;i<=h1;i++){
            for(int j=1;j<=h2;j++){
                dp[i][j]=1.0+p*dp[i][max(0,j-w)]+(1-p)*dp[max(0,i-w)][j];
            }
        }
        printf("%.6f\n",dp[h1][h2]);
    }
	return 0;
}

3.Crossing Rivers

題意：給定路徑長為 D D D的路徑 A B AB AB和 n n n條河，每條河左端距離 A A A為 p p p，長度為 L L L，每條河上有船，速度為 v v v，船的方向，位置隨機，每條河不會相交且不會越界 A B AB AB，陸地上速度為 1 1 1，求從 A A A到 B B B的時間期望，

跟 d p dp dp沒關系，求期望問題，最壞情況是剛到河，船剛開走，時間為： 3 L v \dfrac{3L}{v} v3L?，最好情況是剛到河，船剛開來，時間為： L v \dfrac{L}{v} vL?

因為船的位置線性的，所以平均下來就是 2 L v \dfrac{2L}{v} v2L?，
然后求和即可，最后加上剩下走陸地的時間，就是總期望，

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,d;
int main(){
	int kase=0;
	while(scanf("%d%d",&n,&d)&&(n||d)){
		double ans=0;
		while(n--){
			int p,l;double v;
			cin>>p>>l>>v;
			ans+=2.0*l/v;
			d-=l;
		}
		ans+=d;
		printf("Case %d: %.3f\n\n",++kase,ans);
	}
	return 0;
}