题意
某人在直线上走，直线上有若干格子，起点是1号格，每次这个人都有p概率走1格，1-p概率走二格，有一些格子有地雷，走上去就被爆了，所以要你求你能安全走到终点（可以看成是站在n+1号格）上概率。
思路
每一个格子的概率都可以通过它前两个的格子的概率推出来，这样的话跟斐波那契很像。
联想我们想快速地搞出来一个非常大的fib值的方法是什么？快速幂。
所以这个题我们用快速幂来做。
dp方程其实都不叫dp，叫递推，大概长这个样子：
直接矩阵乘法模版＋快速幂就行。
处理地雷的话，你就先走到地雷那里，停一下，把地雷格的dp值抹成0，然后继续往下走，走到下一个地雷，最后走到终点。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; const int N = 2; int n; struct Mat { double mat[N][N]; }; Mat operator * (Mat a, Mat b) { Mat c; memset(c.mat, 0, sizeof(c.mat)); int i, j, k; for(k = 0; k < N; ++k) { for(i = 0; i < N; ++i) { for(j = 0; j < N; ++j) { c.mat[i][j] += a.mat[i][k] * b.mat[k][j]; } } } return c; } Mat operator ^ (Mat a, int k) { Mat c; int i, j; for(i = 0; i < N; ++i) for(j = 0; j < N; ++j) c.mat[i][j] = (i == j); //初始化为单位矩阵 for(; k; k >>= 1) { if(k&1) c = c*a; a = a*a; } return c; } int main(){ while(cin >> n){ double p = 0; cin >> p; vector<double> mine; mine.push_back(0); for(int i = 1;i <= n;i++){ int tmp = 0; cin >> tmp; mine.push_back(tmp); } sort(mine.begin(),mine.end()); Mat a,b; double dn = 1; for(int i = 1;i < mine.size();i++){ a.mat[0][0] = p; a.mat[0][1] = 1-p; a.mat[1][0] = 1; a.mat[1][1] = 0; Mat c = a^(mine[i]-mine[i-1]); b.mat[0][0] = 0; b.mat[0][1] = 0; b.mat[1][0] = dn; b.mat[1][1] = 0; Mat d = c * b; dn = d.mat[1][0]; } printf("%.7f\n",dn); } return 0; } |
January 26, 2016
#include
#include
#include
using namespace std;
int main()
{
int n, mine[16];
double p;
while (scanf(“%d%lf”, &n, &p) == 2)
{
for (int i = 0; i < n; i++)
scanf("%d", mine + i);
sort(mine, mine + n);
int cur = 1;
double curp = 1;
for (int i = 0; i < n; i++)
{
curp *= 1 – ((1 – p) * pow(p – 1, mine[i] – cur) + 1) / (2 – p);
cur = mine[i] + 1;
}
printf("%.7fn", curp);
}
return 0;
}