首页 > 代码库 > POJ 3744 Scout YYF I
POJ 3744 Scout YYF I
概率$dp$，矩阵优化。
设$dp[i]$为到位置$i$存活的概率，那么如果位置$i$是雷区，$dp[i]=0$，否则$dp[i]=p*dp[i-1]+(1-p)*dp[i-2]$。求出最后一个雷区位置的后一个位置的$dp$值就是答案。长度较大，可以矩阵优化加速一下。输出%$lf$不让过，%$f$过了。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}int n; double p,ans;int a[20];struct Matrix{ double A[4][4]; int R, C; Matrix operator*(Matrix b);};Matrix X, Y, Z;Matrix Matrix::operator*(Matrix b){ Matrix c; memset(c.A, 0, sizeof(c.A)); int i, j, k; for (i = 1; i <= R; i++) for (j = 1; j <= b.C; j++) for (k = 1; k <= C; k++) c.A[i][j] = c.A[i][j] + A[i][k] * b.A[k][j]; c.R=R; c.C=b.C; return c;}void init(double p1,double p2){ Z.A[1][1] = p1, Z.A[1][2] = p2; Z.R = 1; Z.C = 2; Y.A[1][1] = 1, Y.A[1][2] = 0, Y.A[2][1] = 0, Y.A[2][2] = 1; Y.R = 2; Y.C = 2; X.A[1][1] = 0, X.A[1][2] = 1-p, X.A[2][1] = 1, X.A[2][2] = p; X.R = 2; X.C = 2;}void work(int x){ while (x) { if (x % 2 == 1) Y = Y*X; x = x >> 1; X = X*X; } Z = Z*Y;}int main(){ while(~scanf("%d%lf",&n,&p)) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); if(a[1]==1) ans=0; else { bool flag=0; for(int i=1;i<n;i++) if(a[i]+1==a[i+1]) flag=1; if(flag==1) ans=0; else { double p1=0,p2=1; int pos=1, now=1; while(1) { if(a[now]!=pos+1) { init(p1,p2); work(a[now]-1-pos); p1=Z.A[1][1]; p2=Z.A[1][2]; pos=a[now]-1; } double np1=0,np2=(1-p)*p2; pos=pos+2; p1=np1; p2=np2; now++; if(now==n+1) break; } ans=p2; } } printf("%.7f\n",ans); } return 0;}
POJ 3744 Scout YYF I
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。