概率dp+期望dp 题目列表(一)

表示对概率和期望还不是很清楚定义。

目前暂时只知道概率正推,期望逆推,然后概率*某个数值=期望。

为什么期望是逆推的,例如你求到某一个点的概率我们可以求得,然后我们只要运用dp从1~n每次都加下去就好了,这样求出来的就是最后的概率。那么期望呢,就是这个概率*数值就行了。但是有时候这么绕来绕去太麻烦了,我们干脆就逆过来。然后我们发现,根据期望的定义,逆过来以后反正做结果并没有太大的改变,dp从n~1就可以了,并且每次都加上数值,然后在for的途中,这个数值是会不断的乘以概率的,所以期望适合用逆推的方法。

题目列表:

①LightOJ 1030 基础题(一)

②Light OJ 1038 基础题 (二)

③Light OJ 1079 背包+概率(三)

④Light OJ 1104 生日悖论(四)

⑤Light OJ 1248 筛子问题(五)

⑥Light OJ 1265 基础题(四)

一:light OJ 1030 基础题

题目大意:有n个点,每个点有一个val,从1开始出发,到底n个点,每次掷骰子,求到第n个点的期望val是多少?

思路:可以知道对于每个位置,下一个位置只能是后n-i个,所以从这个pos得到的val的期望f(i) = (f(i + 1) + f(i + 2) + … + f(i + 6)) / 6,如果这个位置后不足6,f(i) = (f(i + 1) + … + f(n)) / (n - i)。

期望的代码

//看看会不会爆int! 或者绝对值问题。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ALL(a) a.begin(), a.end()
const int maxn = + ;
int n;
double dp[maxn];
int a[maxn]; int main(){
int T; cin >> T;
for (int t = ; t <= T; t++){
scanf("%d", &n);
memset(dp, , sizeof(dp));
for (int i = ; i <= n; i++){
scanf("%lf", dp + i);
}
for (int i = n; i >= ; i--){
int k = min(, n - i);
for (int j = ; j <= k; j++){
dp[i] += (dp[i + j]) * 1.0 / k;
}
}
printf("Case %d: %f\n", t, dp[]);
}
return ;
}

当然这道题也可以用概率的代码来写,看这个人的博客吧http://www.cnblogs.com/WABoss/p/5296629.html

学习:懂得基本的期望和概率的知识

二:Light OJ 1038 基础题

思路:预处理即可

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const int maxn = 1e5 + ;
double dp[maxn]; int main(){
for (int i = ; i <= maxn - ; i++){
int cnt = ;
double sum = ;
for (int j = ; j * j <= i; j++){
if (i % j == ){
sum += dp[j]; cnt++;
if (j * j != i){
sum += dp[i / j]; cnt++;
}
}
}
sum += cnt;
dp[i] = sum / (cnt - );
}
int t; cin >> t;
for (int i = ; i <= t; i++){
int n; scanf("%d", &n);
printf("Case %d: %.12f\n", i, dp[n]);
}
return ;
}

学习:预处理技能

三:Light oj1079

题目大意:抢银行;一个安全概率p,和银行的个数n;接下去给出每个银行可以抢到的钱,还有抢劫这个银行被抓的概率;问在被抓的概率小于等于p的情况下,最多抢到多少钱;

思路:定义dp[i]目前拿了i元还没有被抓住的最大概率

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const double eps = 1e-;
const int maxn = + ;
double dp[maxn * maxn];///目前拿了j元还没有被抓住的最大概率
int n;
pair<int, double> p[maxn]; int main(){
int kase = ;
int t; cin >> t;
while(t--){
memset(dp, , sizeof(dp));
memset(p, , sizeof(p));
double pro; int sum = ;
scanf("%lf %d", &pro, &n);
for (int i = ; i <= n; i++){
int val; double t;
scanf("%d%lf", &val, &t);
p[i] = mk(val, t);
sum += val;
}
dp[] = ;
for (int i = ; i <= n; i++){
for (int j = sum; j >= p[i].first; j--){
dp[j] = max(dp[j - p[i].first] * ( - p[i].second), dp[j]);
}
}
int ans = ;
for (int i = ; i <= sum; i++){
///printf("%.12f\n", dp[i]);
if (pro - + dp[i] > eps){
ans = i;
}
}
printf("Case %d: %d\n", ++kase, ans);
}
return ;
}

四:生日悖论

题目大意:给你n天,至少有几个人来参加,生日为同一天的概率超过50%?

思路:反过来定义dp[i]表示生日都不相同的概率即可。

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const double eps = 1e-;
const int maxn = 1e5 + ;
double dp[maxn];///生日都不相同的概率 int solve(int n){
memset(dp, , sizeof(dp));
dp[] = 1.0;
for (int i = ; i <= n; i++){
dp[i] = dp[i - ] * (1.0 * (n - i + ) / n);
if ( - dp[i] >= 0.5) return i-;
}
} int main(){
int kase = ;
int t; cin >> t;
while (t--){
int n; scanf("%d", &n);
printf("Case %d: %d\n", ++kase, solve(n));
}
return ;
}

五:Light oj 1248

题目大意:给你n个面的东西,投掷,每个面出现至少一次的概率?

也可以看这个人的http://blog.csdn.net/u011686226/article/details/39928597

定义:dp[i]表示还需要扔i个面所需要投掷次数的期望值。然后每一次投掷是有两种可能性,一种是在已经出现过的面中,另一种是在没有出现过的面中,所以我们可以定义dp[i] = i/n * dp[i] + (n-i)/n * dp[i + 1] + 1;所以移项就好了。

如果想要简便一点想的话,就是6*1+6*(1/2)+6*(1/3)+6*(1/4)+6*(1/5)+6*(1/6)。

不过我还是根据期望的定义来写了。。。先算出概率,再求加权和

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = 1e5 + ;
int n;
double dp[maxn];///定义,目前已经出现i种不同颜色的概率 int main(){
int t; cin >> t;
int kase = ;
while (t--){
scanf("%d", &n);
for (int i = ; i <= n; i++){
dp[i] = 1.0 / i;
}
double ans = ;
for (int i = ; i <= n; i++){
ans += dp[i] * n * 1.0;
}
printf("Case %d: %.12f\n", ++kase, ans);
}
return ;
}

学习:期望的定义是:每个的概率*权值

六:lightOJ 1265

题目大意:有t个老虎,d个鹿,有以下操作

T-M T会吃掉M 
T-D T会吃掉D 
D-D Nothing 
M-D M可以选择杀与不杀D 
T-T 两只T会互相残杀(Two Die)

可以看看这个人的http://blog.csdn.net/challengerrumble/article/details/52528951

思路一:定义dp[i][j]表示还有i只老虎,j只鹿的概率,转移就好了

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
double dp[maxn][maxn];///还有i只老虎,j只鹿的概率
int n, m; int main(){
int T; cin >> T;
for (int kase = ; kase <= T; kase++){
scanf("%d%d", &n, &m);
if (n % == ) {printf("Case %d: %.10f\n", kase, 0.0); continue;}
memset(dp, , sizeof(dp));
dp[n][m] = ;
for (int i = n; i >= ; i--){
for (int j = m; j >= ; j--){
int sum = i * j + i * (i - ) / + i;///总可能性
if (sum == ) continue;
if (j != ) dp[i][j - ] += 1.0 * dp[i][j] * i * j / sum;
if (i >= ) dp[i - ][j] = 1.0 * dp[i][j] * i * (i - ) / / sum;
}
}
double ans = ;
for (int i = ; i <= m; i++) ans += dp[][i];
printf("Case %d: %.10f\n", kase, ans);
}
return ;
}

思路二:定义dp[i] = 目前有i只老虎,老虎全部死亡的概率

因为鹿对我们的存活没有影响,然后我们定义人从来都不杀鹿,这样可以让自己的存活率最大。

所以:

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
double dp[maxn];
int n, m; int main(){
int T; cin >> T;
for (int kase = ; kase <= T; kase++){
scanf("%d%d", &n, &m);
if (n % == ){
printf("Case %d: %.10f\n", kase, 0.0);
continue;
}
dp[n] = 1.0;
for (int i = n; i >= ; i--){
int sum = i * (i - ) / + i;
if (!sum) continue;
if (i >= ) dp[i - ] = dp[i] * i * (i - ) / / sum;
}
printf("Case %d: %.10f\n", kase, dp[]);
}
return ;
}

学习:需要懂得目前哪些东西是无关变量,再加上一点的贪心即可

七:

八:

九:

上一篇:android 开发 制作弹出等待进度条


下一篇:在控制台进行依赖注入(DI in Console)