hdu 4579 Random Walk 概率DP
思路：由于m非常小，只有5。所以用dp[i]表示从位置i出发到达n的期望步数。
那么dp[n] = 0
dp[i] = sigma(dp[i + j] * p (i , i + j)) + 1 . (-m <= j <= m)
从高位向低位暴力消元，每次消去比他高的变量。
如 dp[i] = a1 * dp[i - 1] + a2 * dp[i - 2] …… am * dp[i - m]。
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<iomanip> 5 #include<cmath> 6 #include<cstring> 7 #include<vector> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define MAX 50002 11 using namespace std; 12 double a[MAX][11],p[MAX][11],consts[MAX],q; 13 int c[MAX],cc,l[MAX],r[MAX]; 14 int main(){ 15 int n,m,i,j,k; 16 while(scanf("%d%d",&n,&m)&&(n+m)){ 17 memset(a,0,sizeof(a)); 18 for(i=1;i<=n;i++){ 19 cc=1; 20 for(j=1;j<=m;j++){ 21 scanf("%d",&c[j]); 22 cc+=c[j]; 23 } 24 p[i][m]=1.0; 25 for(j=-m;j<0;j++){ 26 p[i][j+m]=0.3*c[-j]/cc; 27 if(i+j>=1) p[i][m]-=p[i][j+m]; 28 } 29 for(j=1;j<=m;j++){ 30 p[i][j+m]=0.7*c[j]/cc; 31 if(i+j<=n) p[i][m]-=p[i][j+m]; 32 } 33 } 34 for(i=n-1;i>=1;i--){ 35 l[i]=max(1,i-m);//记录该方程的下界 36 r[i]=min(n,i+m);//记录该方程的上界 37 for(j=0;j<r[i]-l[i]+1;j++) 38 a[i][j]=p[i][l[i]+j-i+m]; 39 consts[i]=1.0;//记录常数 40 for(j=r[i];j>i;j--){//将比i高位的变量消去 41 if(j==n) a[i][j-l[i]]=0;//dp[n]=0 42 else{ 43 q=a[i][j-l[i]]; 44 if(fabs(q)<1e-8) continue;//从i到j的概率为0，不需计算 45 for(k=0;k<j-l[j];k++)//将相应变量的系数相加 46 a[i][k+l[j]-l[i]]+=a[j][k]*q; 47 consts[i]+=consts[j]*q;//将常数项相加 48 } 49 } 50 q=1.0-a[i][i-l[i]]; 51 for(j=0;j<r[i]-l[i]+1;j++) 52 a[i][j]/=q; 53 a[i][i-l[i]]=0; 54 consts[i]/=q; 55 } 56 printf("%.2lf ",consts[1]); 57 } 58 return 0; 59 }