题意：n个地雷(n<=10)在长度10^8的坐标轴上,yyf从横坐标为1的点开始,每一步有p的概率向右跳一格,(1-p)的概率向右跳两格(不会踩到中间一格),如果踩到地雷他就会死.问活下来的概率.(其实我们的yyf小朋友是被派去滚雷?)

首先考虑一个暴力的DP.记f[i]为活着经过横坐标为i的点的概率,

如果点i处无地雷则f[i]=f[i-1]*p+f[i-2]*(1-p)

如果点i处有地雷则f[i]=0

由此我们知道,如果yyf能活下来,他一定会经过最后一个地雷右边一格的位置t,所以我们要求的就是f[t],但是直接做显然会TLE.

这时候需要我们的一点直觉,就是DP数组在处理较长一段没有地雷的路径时会趋向于一个定值.可以认为离得很远的地雷对DP状态的贡献小到精度范围内可以忽略不计.通过打表观察发现大概500次就可以保证DP数组收敛到一个定值上(下界可能比500更低,因为已经足够通过本题就没有再试)

因此我们对于每一段没有地雷的区间,如果这段区间长度大于500,就把这段区间的长度缩减至500(具体实现时,如果这段区间的长度和500的差值为delta,就把这段区间后面的所有地雷的横坐标都减去delta),这里注意起点和第一个地雷之间的区间也要缩减(RuntimeError一发).然后再DP,区间总长度不会超过5000,稳稳地过了.如果题目中地雷的数目多一些,就可以卡掉这个做法.(如果要卡掉矩乘,需要坐标范围大到取log之后依然超时,不过范围出成那样也比较容易想到是缩减区间长度)

总结:对于有大范围是简单的特殊情况的问题,我们常常可以通过贪心,找规律等方法有效缩减问题规模,例如这道题和noip2005的过河都考虑到较长一段没有障碍物的区间将不会影响答案,还有poj的up and down用到贪心思想抽象出最短路的建图.
另外这道题网上除了漫天的矩阵快速幂,还有一种神奇的数学方法,见http://blog.csdn.net/qq_26572969/article/details/46825971

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

double f[];

int a[];

bool mine[];

int main(){

  int n;double p;

  while(scanf("%d%lf",&n,&p)!=EOF){

    for(int i=;i<=n;++i){

      scanf("%d",&a[i]);

    }

    sort(a+,a+n+);

    for(int i=;i<n;++i){

      if(a[i+]-a[i]>){

    for(int j=n;j>i;--j){

      a[j]-=(a[i+]-a[i]-);

    }

      }

    }

    memset(f,,sizeof(f));memset(mine,,sizeof(mine));

    for(int i=;i<=n;++i)mine[a[i]]=true;

    f[]=;

    int t=a[n]+;

    for(int i=;i<=a[n];++i){

      if(!mine[i]){

    f[min(i+,t)]+=f[i]*p;f[min(i+,t)]+=f[i]*(-p);

      }

    }

    printf("%.7f\n",f[t]);

  }

  return ;

}