poj3744（概率dp+矩阵快速幂）

女爷i 2022-05-30 12:28 226阅读 0赞

<table style="background-image:url(&quot;http://poj.org/images/table_back.jpg&quot;);font-family:'Microsoft YaHei';"> 
 <tbody> 
  <tr> 
   <td> 
    <div style="text-align:center;font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">
      Scout YYF I 
    </div> 
    <div style="text-align:center;font-family:Arial, Helvetica, sans-serif;font-size:12pt;"> 
     <table> 
      <tbody> 
       <tr> 
        <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
        <td>&nbsp;</td> 
        <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
       </tr> 
       <tr> 
        <td><strong>Total Submissions:</strong>&nbsp;10134</td> 
        <td>&nbsp;</td> 
        <td><strong>Accepted:</strong>&nbsp;2958</td> 
       </tr> 
      </tbody> 
     </table> 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Description</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      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&nbsp; 
     <em>p</em>, or jump two step with a probality of 1- 
     <em>p</em>. Here is the task, given the place of each mine, please calculate the probality that YYF can go through the "mine road" safely. 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Input</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      The input contains many test cases ended with&nbsp; 
     <strong>EOF</strong>. 
     <br>Each test case contains two lines. 
     <br>The First line of each test case is&nbsp; 
     <em>N</em>&nbsp;(1 ≤&nbsp; 
     <em>N</em>&nbsp;≤ 10) and&nbsp; 
     <em>p</em>&nbsp;(0.25 ≤&nbsp; 
     <em>p</em>&nbsp;≤ 0.75) seperated by a single blank, standing for the number of mines and the probability to walk one step. 
     <br>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]. 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Output</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;">
      For each test case, output the probabilty in a single line with the precision to 7 digits after the decimal point. 
    </div><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Sample Input</p><pre style="font-family:'Courier New', Courier, monospace;font-size:12pt;">1 0.5
2
2 0.5
2 4</pre><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Sample Output</p><pre style="font-family:'Courier New', Courier, monospace;font-size:12pt;">0.5000000
0.2500000</pre><p style="font-family:Arial, Helvetica, sans-serif;font-size:18pt;font-weight:bold;color:#0000FF;">Source</p> 
    <div style="font-family:'Times New Roman', Times, serif;font-size:12pt;"> 
     <a href="http://poj.org/searchproblem?field=source&amp;key=POJ+Monthly+Contest+-+2009.08.23" rel="nofollow">POJ Monthly Contest - 2009.08.23</a>, Simon 
    </div></td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\]   \[Go Back\]   \[[Status][]\]   \[[Discuss][]\]

思路：

第一反应是从头暴力可以通过dp\[i\]=p\*dp\[i-1\] + (1-p)\*dp\[i-2\]状态转移方程求出dp\[i\]， 但是地雷范围太大 ， 会T

很难想到一点通过构造矩阵求出dp\[i\], 我构造的是

\[ dp\[i-1\], dp\[i-2\] \] \*  p          1

(1-p)      0

构造完成后  可以将地雷分区间 ， 使得每个区间最后一个点是地雷， 这样顺利通过该区间的概率就是 1-该点概率， 最后每个区间用乘法原理。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int maxn=1e3+10;
    
    int n;
    int pos[20];
    double p;
    
    struct Matrix{
        double m[2][2];
    };
    
    /*
        构造矩阵 p      1
                  (1-p)  0
    */
    
    Matrix mul_M(Matrix a, Matrix b){
    
        Matrix c;
    
        for(int i=0; i<2; i++)
        {
            for(int j=0; j<2; j++)
            {
                c.m[i][j]=0;
                for(int k=0; k<2; k++)
                    c.m[i][j]+= a.m[i][k] * b.m[k][j];
            }
        }
        return c;
    }
    
    Matrix pow_M(Matrix x, int num){
    
        Matrix ans;
        ans.m[0][0]=ans.m[1][1]=1;
        ans.m[0][1]=ans.m[1][0]=0;
    
        while(num){
    
            if(num&1)
            {
                ans=mul_M(ans, x);
            }
    
            x=mul_M(x, x);
            num>>=1;
        }
        return ans;
    }
    
    int main(){
        while(~scanf("%d%lf", &n, &p)){
            for(int i=1; i<=n; i++)
                scanf("%d", &pos[i]);
            sort(pos+1, pos+1+n);
    
            Matrix v;
            v.m[0][0]=p; v.m[0][1]=1; v.m[1][0]=1-p; v.m[1][1]=0;
    
            double ans=1;
            for(int i=1; i<=n; i++)
            {
    
                Matrix tmp=pow_M(v, pos[i]-pos[i-1]-1);
                ans*=(1-tmp.m[0][0]);
            }
    
    
            printf("%.7lf\n", ans);
    
        }
        return 0;
    }

[Submit]: http://poj.org/submit?problem_id=3744
[Status]: http://poj.org/problemstatus?problem_id=3744
[Discuss]: http://poj.org/bbs?problem_id=3744