hdu 4089 不错的DP 北京现场赛题

本文主要是介绍hdu 4089 不错的DP 北京现场赛题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=4089

还有疑惑，需要重新推：
但是学到的：
1、A=a+b+c  abc是三种情况，那么P(A)=a*P(a->事件)+b*P(b->事件)+c*P(c->事件);

a->事件意思是 在a情况下的事件，就是全概率公式的思想吧

2、一定注意每一步会不会出现分母为0 的情况，以及预处理的时候对于一些特殊情况导致自己的式子会出现分母为0的排除掉

3、概率DP经常出现推出了式子但是自己不会写代码的情况，那么就模拟计算，注意迭代找计算规律

题解参考着两个：
http://blog.csdn.net/morgan_xww/article/details/6920236

http://88094657.blog.163.com/blog/static/147251759201222781153704/

至于第一篇博客提到的TLE的事情，目测是分母出现0了，其实算法挺多的，不一定用那个：
可以这样：（因为dp[i][i]和dp[i][1] c[j]已经算出来了）

            for(int j=2;j<i;j++){dp[i][j]=p21*dp[i][j-1]+c[j];}

但是不知道为啥这个不对。。

            for(int j=2;j<i;j++){dp[i][j]=p21*dp[i][i] + p31*dp[i-1][j-1];if(j<=k) dp[i][j]+=p41;}

AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const int MAXN = 2000+5;
double dp[MAXN][MAXN],pp[MAXN];
double c[MAXN];int main()
{//IN("hdu4089.txt");int n,m,k;double p1,p2,p3,p4,p21,p31,p41;while(~scanf("%d%d%d",&n,&m,&k)){CL(dp,0);scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);if(abs(1.0-p1-p2)<EPS || abs(p4)<EPS){puts("0.00000");continue;}dp[1][1]=p4/(1.0-p1-p2);p21=p2/(1.0-p1);p31=p3/(1.0-p1);p41=p4/(1.0-p1);c[1]=p41;c[0]=1.0;///pp[0]=1.0;for(int i=1;i<=n;i++)pp[i]=p21*pp[i-1];for(int i=2;i<=n;i++){for(int j=2;j<=k;j++)c[j]=p31*dp[i-1][j-1]+p41;for(int j=k+1;j<=n;j++)c[j]=p31*dp[i-1][j-1];double tmp=0.0;for(int j=1;j<=i;j++)tmp+=pp[i-j]*c[j];dp[i][i]=tmp/(1.0-pp[i]);dp[i][1]=p21*dp[i][i]+p41;/*for(int j=2;j<i;j++){dp[i][j]=p21*dp[i][i] + p31*dp[i-1][j-1];if(j<=k) dp[i][j]+=p41;}*/for(int j=2;j<i;j++)dp[i][j]=p21*dp[i][j-1]+c[j];}printf("%.5lf\n", dp[n][m]);}return 0;
}

这篇关于hdu 4089 不错的DP 北京现场赛题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---