hdu 4405 Aeroplane chess题解

1、动归，用f和p两个数组分别记录i点的期望值和概率值。m记录飞行通道。m也要开100000.并且要做预处理，即将可以连续飞行到通道连起来即： for(i=1;i<n;i++) while(m[m[i]]!=0) m[i]=m[m[i]];

2、从0开始往后更新，如果没有通道即： f[i+j]+=(f[i]+p[i])*r; p[i+j]+=p[i]*r;否则： f[m[i+j]]+=(f[i]+p[i])*r; p[m[i+j]]+=p[i]*r;

3、以下是代码：#include<iostream>#include争犸禀淫<stdio.h>#include<string.h>double f[100010],p[100010];int main(){ //freopen("in","r",stdin); int m[100010]; double r=(1.0)/(6.0); int i,j,n,M,t,tmp; double ret; while(scanf("%d%d",&n,&M)&&n!=0){ memset(m,0,sizeof(m)); memset(f,0,sizeof(f)); memset(p,0,sizeof(p)); p[0]=1; for(i=0;i<M;i++){ scanf("%d%d",&t,&tmp); m[t]=tmp; } for(i=1;i<n;i++) while(m[m[i]]!=0) m[i]=m[m[i]]; for(i=0;i<n;i++){ for(j=1;j<=6;j++){ if(m[i+j]!=0){ f[m[i+j]]+=(f[i]+p[i])*r; p[m[i+j]]+=p[i]*r; } else { f[i+j]+=(f[i]+p[i])*r; p[i+j]+=p[i]*r; } } } for(i=n+1;i<n+6;i++) f[n]+=f[i]; printf("%.4lf\n",f[n]); } return 0;}