POJ 3744 Scout YYF I-白红宇

POJ 3744 Scout YYF I

阅读量：7226 次

发布时间：2019-06-29

本文共 1611 字，大约阅读时间需要 5 分钟。

概率$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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               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 
               
                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

转载于:https://www.cnblogs.com/zufezzt/p/6295965.html

你可能感兴趣的文章