POJ 3744 Scout YYF I 矩阵快速幂优化--概率dp

点击打开链接

Scout YYF I

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5416 Accepted: 1491

Description

YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties, YYF is now at the start of enemy's famous "mine road". This is a very long road, on which there are numbers of mines. At first, YYF is at step one. For each step after that, YYF will walk one step with a probability of p, or jump two step with a probality of 1-p. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely.

Input

The input contains many test cases ended with EOF.
Each test case contains two lines.
The First line of each test case is N (1 ≤ N ≤ 10) and p (0.25 ≤ p ≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step.
The Second line of each test case is N integer standing for the place of N mines. Each integer is in the range of [1, 100000000].

Output

For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point.

Sample Input

1 0.5 2 2 0.5 2 4

Sample Output

0.5000000 0.2500000

Source

POJ Monthly Contest - 2009.08.23, Simon

有n个雷放在1~100000000的位置上,初始位置是1,走一步的概率是p,走两步的概率是1-p,求顺利通过所有雷的概率。 状态转移方程:dp[i]=p*dp[i-1]+(1-p)*dp[i-2],如果直接算会MLE或者TLE,可以转换成用矩阵快速幂求解。 POJ 3744 Scout YYF I 矩阵快速幂优化--概率dp
vcDXtcS4xcLKKDEtssi1vcDXtcS4xcLKo6mjrMi7uvPA27PLvs3Kx7TwsLihozwvc3Ryb25nPgo8YnI+Cgo8cHJlIGNsYXNzPQ=="brush:java;">#include #include #include using namespace std; double p; int pos[17]; struct Matrax { double m[2][2]; }a,per,tmp; void init()//建立矩阵 { a.m[0][0]=p;a.m[0][1]=1-p; a.m[1][0]=1;a.m[1][1]=0; per.m[0][0]=1;per.m[0][1]=0; per.m[1][0]=0;per.m[1][1]=1; } Matrax multi(Matrax a,Matrax b)//矩阵相乘 { Matrax c; for(int i=0;i>=1;pp=multi(pp,pp);} } return ans; } int main() { int n; while(scanf("%d%lf",&n,&p)!=EOF) { bool no=false; double ans=1; memset(pos,0,sizeof(pos)); for(int i=1;i

分类:默认分类 时间:2012-05-06 人气:8
本文关键词:
分享到:

相关文章

  • poj 3744 Scout YYF I (矩阵快速幂+概率dp) 2012-03-16

    Scout YYF I Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4374 Accepted: 1141 Description YYF is a couragous scout. Now he is on a dangerous mission which is to penetrate into the enemy's base. After overcoming a series difficulties, YYF

  • POJ 3744 Scout YYF I (概率DP+矩阵快速幂) 2013-04-25

    题目地址:POJ 3744 一个线性概率DP递推式。dp[i]=p*dp[i-1]+(1-p)*dp[i-2]。但是i的值太大。所以可以分成n次,每一次中间过程的纯递推过程用矩阵快速幂来优化。只要想到矩阵快速幂就挺简单了。 代码如下: #include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi

  • poj 2096 Collecting Bugs (概率dp) 2012-08-02

    /* dp求期望 逆着递推求解 题意: 一个软件有s个子系统,会产生n种bug 某人一天发现一个bug,这个bug属于一个子系统,属于一个分类 每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n 问发现n种bug,每个子系统都发现bug的天数的期望。 求解: dp[i][j]表示已经找到i种bug,j个系统的bug,达到目标状态的天数的期望 dp[n][s]=0,dp[0][0]为所求答案 dp[i][j]由四种状态转化而来 1:dp[i][j] 发现一个状态已有i个分类j个系统

  • poj 1322 Chocolate (概率dp) 2012-10-20

    ///有c种不同颜色的巧克力,一个个的取,当发现有相同的颜色的就吃掉,去了n个后,到最后还剩m个的概率 ///dp[i][j]表示取了i个还剩j个的概率 ///当m+n为奇时,概率为0 # include # include # include # include using namespace std; double dp[1010][1010]; int main() { int i,j,n,m,c; while(~scanf("%d",&c),c) { scanf("%d%d",

  • poj-3071-Football-概率模拟 2012-11-06

    直接模拟比赛过程。 ans[i][j]:第i次比赛,第j个人获胜的概率。 #include #include #include #include using namespace std; double maps[1001][1001]; double ans[1001][1001]; int main() { int n,m,i,j,k; while(~scanf("%d",&m)&&(m!=-1)) { n=1maxx) { maxx=ans[m][i]; st=i;

  • POJ 2096 Collecting Bugs 概率dp(水 2013-04-13

    题目链接:点击打开链接 题意: 点击打开链接 对于这里的dp做法是: 写一个状态x,然后把从x转移出去的方程写出来,即 x = y1+y2+··· 其中所有的yi都是已知的。 这样我们就会得到一个方程是从未知到已知。 但是dp是由已知到未知。所以我们再呵呵回来。。 #include #include #include #include #include #include #include using namespace std; const int N = 1005; double dp[N][

  • poj 2151 Check the difficulty of problems(概率DP) 2014-09-22

    Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 4680 Accepted: 2049 Description Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect

  • 概率dp+状态压缩HDU4336 2012-01-29

    Card Collector Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit Status Practice HDU 4336 Appoint description: System Crawler (2014-10-23) Description In your childhood, do you crazy for collecting the beautiful cards in

  • poj2096--Collecting Bugs(概率dp第二弹,求期望) 2012-03-04

    Collecting Bugs Time Limit: 10000MS Memory Limit: 64000K Total Submissions: 2678 Accepted: 1302 Case Time Limit: 2000MS Special Judge Description Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stuff,

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.161 (s). 10 q(s)