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

[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-04-19
  • 长效机制加速推进 楼市下半年或持续降温 2019-04-19
  • 树立文化自信 创新节庆模式 2019-04-19
  • 朝韩将军级会谈时隔11年后在板门店重启 2019-04-19
  • 经济日报多媒体数字报刊 2019-04-18
  • 搞好公有制就是好,故得出结论:计划经济好。 2019-04-18
  • 云南理发店老板涉嫌杀害女演员因办卡纠纷起杀心 2019-04-18
  • 南海网-海南新闻网-权威媒体 海南门户 2019-04-17
  • 海底捞回应侵犯音乐人林海著作权:已停止播放 2019-04-17
  • 自然型社会和规则性社会,是会随着科技的改变而发生改变的,当然只有规矩也就是制度才能规范人的行为,所以国家是不会灭亡的,但国家的形式是会发生改变的。 2019-04-17
  • 惊艳!上外学子英译60首热门中文歌  让世界倾听中国 2019-04-16
  • 西安,给盲人朋友留一条路吧…无障碍设施盲道-编辑整合 2019-04-16
  • 的确如此。报刊亭取消的确是短视行为。把报刊亭设计的现代化一些,与城市绿化衔接起来,相得益彰,成为文化一景多好。 2019-04-16
  • 让更多企业和劳动者尝到协商的“甜头” 2019-04-16
  • 2014金家岭财富论坛嘉宾云集(二) 2019-04-15
  • 989| 471| 154| 17| 546| 304| 113| 469| 442| 868|