首页 > 代码库 > POJ 3744 Scout YYF I 概率dp+矩阵快速幂
POJ 3744 Scout YYF I 概率dp+矩阵快速幂
题目链接：点击打开链接
题意：
离散的一维坐标轴
开始人在0点，每次有p概率向→跳一格， 1-p概率跳两格。
下面n个数表示在这些格子上有地雷，踩到就屎。
问安全通过的概率。
思路：
若不考虑地雷，跳到某一格的概率就是dp[i] = dp[i-1]*p + dp[i-2]*(1-p)
很容易想到转移方程： dp[i]=p*dp[i-1]+(1-p)*dp[i-2];
但是由于坐标的范围很大，直接这样求是不行的，而且当中的某些点还存在地雷。
N个有地雷的点的坐标为 x[1],x[2],x[3]```````x[N].
我们把道路分成N段：
1~x[1];
x[1]+1~x[2];
x[2]+1~x[3];
`
`
`
x[N-1]+1~x[N].
这样每一段只有一个地雷。我们只要求得通过每一段的概率。乘法原理相乘就是答案。
对于每一段，通过该段的概率等于1-踩到该段终点的地雷的概率。
就比如第一段 1~x[1]. 通过该段其实就相当于是到达x[1]+1点。那么p[x[1]+1]=1-p[x[1]].
但是这个前提是p[1]=1,即起点的概率等于1.对于后面的段我们也是一样的假设，这样就乘起来就是答案了。
对于每一段的概率的求法可以通过矩阵乘法快速求出来。
<pre name="code" class="cpp">#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
template <class T>
inline bool rd(T &ret) {
char c; int sgn;
if(c=getchar(),c==EOF) return 0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
template <class T>
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if(x>9) pt(x/10);
putchar(x%10+'0');
}
using namespace std;
#define Matr 3 //矩阵大小,注意能小就小
typedef double ll;
struct mat {
ll a[Matr][Matr];
int size;
mat(int siz) {
size=siz;
for(int i = 0; i < size; i++)
for(int j = 0; j < size; j++)
a[i][j] = 0;
}
};
void print(mat m){
printf("%d\n",m.size);
for(int i=0;i<m.size;i++)
{
for(int j=0;j<m.size;j++)cout<<m.a[i][j];
puts("");
}
}
mat multi(mat m1,mat m2)//两个相等矩阵的乘法，对于稀疏矩阵，有0处不用运算的优化
{
mat ans=mat(m1.size);
for(int i=0;i<m1.size;i++)
for(int j=0;j<m2.size;j++)
if(m1.a[i][j])//稀疏矩阵优化
for(int k=0;k<m1.size;k++)
ans.a[i][k] += m1.a[i][j]*m2.a[j][k];
return ans;
}
mat quickmulti(mat m,int n)//二分快速幂
{
mat ans=mat(m.size);
for(int i=0;i<m.size;i++)ans.a[i][i]=1;
while(n)
{
if(n&1)ans=multi(m,ans);
m=multi(m,m);
n>>=1;
}
return ans;
}
double p;
int n, a[20];
/*
dp[i] = dp[i-1]*p + dp[i-2]*(1-p);
*/
mat work(int step){
mat y = mat(2);
y.a[0][0] = p; y.a[0][1] = 1;
y.a[1][0] = 1-p;
y = quickmulti(y, step);
return y;
}
int main(){
while(cin>>n>>p){
for(int i = 1; i <= n; i++)
rd(a[i]);
sort(a+1, a+1+n);
mat y = work(a[1]-1);
double ans = 1 - y.a[0][0];
for(int i = 2; i <= n; i++)
{
if(a[i-1] == a[i])continue;
y = work(a[i]-a[i-1]-1);
ans *= 1-y.a[0][0];
}
printf("%.7f\n", ans);
}
return 0;
}
POJ 3744 Scout YYF I 概率dp+矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。