题意:

  一条路上有 $n$ 个地雷,YYF 从位置 $1$ 出发,走一步的概率为 $p$,走两步的概率是 $(1-p)$。求 YYF 能顺利通过这条路的概率。

数据范围: $1\leq n \leq 10$,$0.25\leq p\leq 0.75$,输入的 $n$ 个位置的范围:$[1,1e8]$

分析:

  从前往后推,状态转移方程:$dp[i]=dp[i-1]*p+dp[i-2]*(1-p)$,其中 $dp[1]=1$,有地雷的位置 $dp[i]=0$。如果直接算,必然超时,可以用矩阵快速幂分段优化。

坑点:输入的 $n$ 个位置不一定有序。

代码:

 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <algorithm>
 using namespace std;
 ];
 double p;
 struct matrix
 {
     ][];
     void clc()
     {
         ;i<;i++)
             ;j<;j++)
                 mat[i][j]=;
     }
     void eye()
     {
         ;i<=;i++)
             mat[i][i]=;
     }
     matrix operator *(const matrix b)const
     {
         matrix res;
         res.clc();
         ;i<=;i++)
         {
             ;k<=;k++)
             {
                 ;j<=;j++)
                     res.mat[i][j]=(res.mat[i][j]+mat[i][k]*b.mat[k][j]);
             }
         }
         return res;
     }
 };
 matrix mpow(matrix a,int b)
 {
     matrix res;
     res.clc();
     res.eye();
     while(b)
     {
         )
             res=res*a;
         a=a*a;
         b>>=;
     }
     return res;
 }
 void init(matrix &a)
 {
     a.clc();
     a.mat[][]=;
 }
 void init2(matrix &b)
 {
     b.clc();
     b.mat[][]=p;
     b.mat[][]=;
     b.mat[][]=-p;
 }
 int main()
 {
     int n,x,last;
     while(scanf("%d%lf",&n,&p)!=EOF)
     {
         ;i<=n;i++)
             scanf("%d",&a[i]);
         sort(a+,a++n);
         matrix A,B;
         init(A);
         init2(B);
         ;
         last=;
         ;i<=n;i++)
         {
             A=A*mpow(B,a[i]-last);//cout<<"A="<<A.mat[1][2]<<endl;
             A.mat[][]=;
             last=a[];
         }
         A=A*B;
         printf(][]);
     }
     ;
 }

最新文章

  1. 排序算法----调用库函数qsort进行快速排序
  2. bzoj3388(神奇的解法)
  3. maven添加本地jar包
  4. python对象
  5. &lt;&lt;Design Patterns&gt;&gt; Gang of Four
  6. 模拟实现ORM实例
  7. Github教程(2)
  8. C#中的lock关键字
  9. XtraBackup原理3
  10. How to Analyze Java Thread Dumps--reference
  11. Java文件File操作一:文件的创建和删除
  12. kbhit()
  13. 用SpriteBuilder简化&quot;耕牛遍地走&quot;的动画效果(二)
  14. Java:全局变量(成员变量)与局部变量
  15. [转]Spring通过@Value注解注入属性的几种方式
  16. 【English】主语从句的引导词是如何选择?
  17. HDU 2147 kiki&#39;s game(博弈经典题)
  18. Linux各种类型压缩包解压缩方法
  19. Leetcode--680. Valid Palindrome II(easy)
  20. cordova开发ios炸鸡

热门文章

  1. JSP&amp;Servlet学习笔记----第6章
  2. Spacemacs安装
  3. 题解 UVA1479 【Graph and Queries】
  4. Scala 学习(10)之「集合 」
  5. 自定义内建模块 - Python Build Your Own Built-In Module
  6. Rust入坑指南:步步为营
  7. MSSqlServer访问远程数据库
  8. Hexo搭建静态博客踩坑日记(二)
  9. pytorch之 compare with numpy
  10. ospf路由协议源码学习