題目地址：POJ 3744
一個線性概率DP遞推式。dp[i]=p*dp[i-1]+(1-p)*dp[i-2]。但是i的值太大。所以可以分成n次，每一次中間過程的純遞推過程用矩陣快速冪來優化。只要想到矩陣快速冪就挺簡單了。
代碼如下：
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=100000000; const int INF=0x3f3f3f3f; const double eqs=1e-8; int a[20]; double dp[20]; struct Matrix { double ma[3][3]; }init, res; Matrix Mult(Matrix f1, Matrix f2) { int i, j, k; Matrix tmp; memset(tmp.ma,0,sizeof(tmp.ma)); for(i=0;i<2;i++){ for(j=0;j<2;j++){ tmp.ma[i][j]=0; for(k=0;k<2;k++){ tmp.ma[i][j]+=f1.ma[i][k]*f2.ma[k][j]; } } } return tmp; } Matrix Pow(Matrix x, int k) { Matrix tmp; int i, j; for(i=0;i<2;i++) for(j=0;j<2;j++) tmp.ma[i][j]=(i==j); while(k){ if(k&1) tmp=Mult(tmp,x); x=Mult(x,x); k>>=1; } return tmp; } int main() { int n, i, flag, k; double p, p1, p2; while(scanf("%d%lf",&n,&p)!=EOF){ for(i=1;i<=n;i++){ scanf("%d",&a[i]); } a[0]=0; sort(a,a+n+1); flag=0; for(i=1;i<=n;i++){ if(a[i]==a[i-1]+1||a[i]==1){ flag=1; break; } } if(flag){ printf("0.0000000\n"); continue ; } init.ma[0][0]=p;init.ma[0][1]=1-p; init.ma[1][0]=1;init.ma[1][1]=0; p1=1; for(i=1;i<=n;i++){ if(a[i]-a[i-1]==2){ p1=p1*(1-p); } else{ p2=p1*p; k=a[i]-a[i-1]-3; res=Pow(init,k); p1=(p2*res.ma[0][0]+p1*res.ma[0][1])*(1-p); //printf("k--%d\n",k); } //printf("%.7f\n",p1); } printf("%.7f\n",p1); } return 0; }
javascript中dom實現可以使我們在a
µÚÁùÊ®½²£ºËÄ´ó×é¼þÖ®BroadcastR
用遞歸方法對二叉樹進行層次遍歷，遞歸二叉樹層次遍
leetcode筆記：Sort Colors 一. 題目描述
VC++函數只被調用一次，vc函數調用一次如何保證某個函數只
