现在的位置: 首页 > 算法 > 正文

[poj 3853]Loops[概率DP入门题]

2019年03月01日 算法 ⁄ 共 1833字 ⁄ 字号 评论关闭

秒速赛车公式 www.l19l7.cn 这种题主要就是推状态转移方程..推公式
解析:
设dp[i][j]表示(i,j)到(R,C)需要消耗的能量[这个定义很重要!]
则:
dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2;(走一步,额外消耗能量2)
化简得到:
dp[i][j]=p2[i][j]*dp[i][j+1]/(1-p1[i][j])+p3[i][j]*dp[i+1][j]/(1-p1[i][j])+2/(1-p1[i][j]);
注意一种情况就是p1[i][j]==1的情况。(除0错误)
题目只是保证答案小于1000000.但是有的点可能永远都不可能到达的。
所以这样的点出现p1[i][j]是允许的。
否则就会WA了。

转自://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html

#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=1010;
const double eps=1e-5;
double dp[MAXN][MAXN];
double p1[MAXN][MAXN];
double p2[MAXN][MAXN];
double p3[MAXN][MAXN];

int main()
{
    int R,C;
    while(scanf("%d%d",&R,&C)!=EOF)
    {
        for(int i=1;i<=R;i++)
          for(int j=1;j<=C;j++)
            scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);
        dp[R][C]=0;///倒着推!
        for(int i=R;i>=1;i--)
          for(int j=C;j>=1;j--)
          {
              if(i==R&&j==C)continue;
              if(fabs(1-p1[i][j])<eps)continue;
              dp[i][j]=p2[i][j]/(1-p1[i][j])*dp[i][j+1]+p3[i][j]/(1-p1[i][j])*dp[i+1][j]+2/(1-p1[i][j]);
          }
        printf("%.3lf\n",dp[1][1]);
    }
    return 0;
}

自己敲一遍:

#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 1005;
const double EPS = 1e-5;
double dp[MAXN][MAXN],p1[MAXN][MAXN],p2[MAXN][MAXN],p3[MAXN][MAXN];
/**
dp[i][j] 表示从(i,j)到(R,C)耗费的能量
状态转移:
dp[i][j] = (p2[i][j]*dp[i+1][j] + p3[i][j]*dp[i][j+1] + 2) / (1 - p1[i][j]);
注意避免除0错误
**/
int main()
{
    int R,C;
    while(scanf("%d%d",&R,&C)==2)
    {
        for(int i=1;i<=R;i++)
            for(int j=1;j<=C;j++)
                scanf("%lf%lf%lf",p1[i]+j,p2[i]+j,p3[i]+j);
        dp[R][C] = 0;///由于没有越界的操作,也不涉及"坑"的值,也就不需要memset了,只要初始化终点即可
        for(int i=R;i>0;i--)
            for(int j=C;j>0;j--)
            {
                if(i==R && j==C)    continue;
                if(fabs(1 - p1[i][j])<EPS)  continue;///为什么这里不赋值?
                ///如果到达这里的概率是p,那么从这里到终点的能量应该是INF,那么总的期望..?
                ///显然也是INF.也就是说只要有可能走不出,那么期望就是走不出.
                ///从AC的情况反推数据,应该是,有p1==1的点,但是左和上数据[保证]不会走到这一点
                ///所以这一点的值是无所谓的,只要在计算它自己的时候避免一下除零错误,跳过就行了
                ///好吧,其实题目说<1000000,意思不只是限制在int内,还表明了没有INF的情况...
                dp[i][j] = (p2[i][j]*dp[i][j+1] + p3[i][j]*dp[i+1][j] + 2) / (1 - p1[i][j]);
            }
        printf("%.3lf\n",dp[1][1]);
    }
}

但是目测很慢的样子...

【上篇】
【下篇】

抱歉!评论已关闭.

  • 第十六届中国经济论坛 2019-06-26
  • 拜博口腔医疗集团创始人、董事长黎昌仁获第十二届人民企业社会责任奖年度人物奖 2019-06-26
  • 县名解析晋城高平市地名来历 2019-06-25
  • “网络党课”第二课 杨禹《为美好生活而奋斗》 2019-06-25
  • 自然规律是不可改变的,社会规律是可以改变的。这是自然科学与社会科学的区别之一。 2019-06-25
  • 香港有祖国全面支持<br>港人对未来满怀憧憬 2019-06-25
  • 中央第四环保督察组向江西移交1034件信访问题线索 2019-06-24
  • 第十二届中国(南宁)国际园林博览会吉祥物正式发布 2019-06-24
  • C级总销量迫近A4L 宝马3系乏力 2019-06-24
  • 包车司机借口“学炒股”敲开门 抢钱后杀人抛尸 2019-06-23
  • 临汾“尧王杯”马拉松赛激情开跑 2019-06-23
  • 我们包住内力,在不断变化中寻找契机可出击可借力亦可卸力。 2019-06-23
  • “ONE NIGHT 给小孩”北京站探访周迅刘雯共奏可爱“交响曲” 2019-06-22
  • 爱护民生:什么基金都不能买,即使获利,也不会给分多少红利,只是意思意思。 2019-06-22
  • 三颗迄今最年轻行星现形 2019-06-22
  • 016组选的关系 博彩业排行榜 曾道人免费一码中特码 六合图库2019官网 台湾码最快开奖直播 京东彩票商品 北京快三最快开奖结果 中国福利彩票3d图形 会员料三肖中特公开 重庆幸运农场水果走势图2019新版 河北十一选五任五最高遗漏多少期 一个赌徒10年赌博经验 重庆幸运农场早上几点开始 安徽快三查询 500彩票网不能买3d