本文主要是介绍kotori和抽卡(二)-概率dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:https://ac.nowcoder.com/acm/problem/50044
Problem
给出四张卡片被抽到的概率,现在有n张卡片,问抽到m张R卡片的概率是多少。
Soultion
其它三张卡片的概率都是没用的,只需要知道R卡片的概率就行。
对于第i次抽,可能抽到R卡片,也可能抽不到R卡片,两种情况,考虑用dp来做。
动态规划三步走:
找状态:dp[i][j]表示抽了i次中抽到j次R卡片的概率
状态转移:
赋初值:dp[0][0] = 0,dp[i][0] = dp[i-1][0]*0.2
Code
#include <bits/stdc++.h>
#define ll long long
#define pir pair<int,int>
#define debug(x) cout << #x << ":" << x << '\n'
const int N = 5e5+7;
const int mod = 1e9+7;
const ll ds = 1e15;
const double eps = 1e-8;using namespace std;int n,m,k,x;
double dp[3005][3005],a[N],p;
void solve(){scanf("%d%d",&n,&m);dp[0][0] = 1;for(int i = 1; i <= n; i++){dp[i][0] = dp[i-1][0]*0.2;for(int j = 1; j <= i; j++){dp[i][j] = (dp[i-1][j]*0.2+dp[i-1][j-1]*0.8);}}printf("%.4f\n",dp[n][m]);
}int main(){// int t;// cin >> t;// while(t--)solve();//system("pause");return 0;
}
这篇关于kotori和抽卡(二)-概率dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!