Random WalkTime Limit: 5000/2000 MS (Java/Others)Memory Limit: 65535/65536 K (Java/Others)Total Submission(s): 200Accepted Submission(s): 117
Problem Description
Yuanfang is walking on a chain. The chain has n nodes numbered from 1 to n. Every second, he can move from node i to node j with probability:
c(i,j) is an element in a given parameter matrix which is n×m. (1 <= c(i, j) <= 9)Yuanfang wants to know the expectation time for him to walk from node 1 to node n.
Input
There are no more than 10 test cases.In each case, there are two integers n (2 <= n <= 50000), m (1 <= m <= 5), in the first line, meaning that there are n nodes and the parameter matrix is n×m . There are m integers in each of the next n lines which describe the parameter matrix .The input ends with 0 0.
Output
For each case, output the expectation time for Yuanfang to walk from node 1 to node n in one line. The answer should be rounded to 2 digits after decimal point.
Sample Input
3 11115 21 22 13 22 31 30 0
Sample Output
6.948.75
Source
2013ACM-ICPC杭州赛区全国邀请赛
/* ***********************************************Author:CKbossCreated Time :2015年05月06日 星期三 08时54分13秒File Name:HDOJ4579_2.cpp************************************************ */#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <cmath>#include <cstdlib>#include <vector>#include <queue>#include <set>#include <map>using namespace std;const int maxn=50050;const double eps=1e-6;double c[maxn][10];double p[maxn][20];double a[maxn][10];double b[maxn];double dp[maxn];int n,m;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&m)!=EOF){if(n==0&&m==0) break;for(int i=1;i<=n;i++){double s=0;for(int j=1;j<=m;j++){scanf("%lf",&c[i][j]);s+=c[i][j];}c[i][0]=s;}for(int i=1;i<=n;i++){/// Leftdouble sum=0.;for(int j=1;j<=m;j++){if(i-j<1) continue;p[i][m-j]=0.3*c[i][j]/(1+c[i][0]);sum+=p[i][m-j];}/// Rightfor(int j=1;j<=m;j++){if(i+j>n) continue;p[i][m+j]=0.7*c[i][j]/(1+c[i][0]);sum+=p[i][m+j];}p[i][m]=-sum;b[i]=-1;}for(int i=1;i<=m+1&&i<=n;i++) a[1][i]=p[1][m+i-1];for(int i=2;i<n;i++){int start=max(1,i-m);int end=min(n,i+m);for(int j=start;j<i;j++) // 第j行去减第i行{if(fabs(p[i][m-i+j])<eps) continue;double t=p[i][m-i+j]/a[j][1];for(int k=1;k<=m+1&&j+k-1<=n;k++){p[i][m-i+j+k-1]-=a[j][k]*t;}b[i]-=t*b[j];}for(int j=1;j<=end-i+1;j++){a[i][j]=p[i][m+j-1];}}dp[n]=0;for(int i=n-1;i>=1;i–){for(int j=2;j<=m+1&&i+j-1<=n;j++)b[i]-=dp[i+j-1]*a[i][j];dp[i]=b[i]/a[i][1];}printf("%.2f\n",dp[1]);}return 0;}
，一直觉得人应该去旅行，在年轻的时候，趁着有脾气装潇洒，
