http://acm.hdu.edu.cn/showproblem.php?pid=4050
题意:
现在主角站在0处,需要到达大于n的位置
主角要进入的格子有三种状态:
0. 不能进入
1. 能进入左脚,下一步出右脚
2. 能进入右脚,下一步出左脚
3. 两只脚都能进入,而且下一步迈出左右脚都可.
也就是说,如果只有1,2种状态的格子,那么主角只能重复左脚-右脚-左脚...或者右脚-左脚-右脚
但是有了状态为3的格子,就能够左脚-左脚-左脚这样走路
设e[i][sta]为主角在编号为i的方格状态为sta的概率,sta为1,2,3,分别代表踏入的是下一步右脚,下一步左脚,两只脚都可以的格子
并设kp1[i+a][i+j]从i+a开始到i+j-1右脚无法踏入的概率,kp2[i+a][i+j]从i+a开始到i+j-1左脚无法踏入的概率,kp3[i+a][i+j]为两只脚都无法踏入概率,
则:
e[i][1]+=(e[i+j][2]+1)*kp1*p2[i+j]+(e[i+j][3]+1)*kp1*p3[i+j];
e[i][2]+=(e[i+j][1]+1)*kp2*p1[i+j]+(e[i+j][3]+1)*kp2*p3[i+j];
e[i][3]+=(e[i+j][1]+1)*kp3*p1[i+j]+(e[i+j][2]+1)*kp3*p2[i+j]+(e[i+j][3]+1)*kp3*p3[i+j];
明显e[0][3]为答案
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=2e3+;
const double eps=1e-;
int n,a,b;
double p0[maxn],p1[maxn],p2[maxn],p3[maxn];
double e[maxn][];
void calc(){
for(int i=n;i>=;i--){
memset(e[i],, sizeof e[i]);
double kp1=,kp2=,kp3=;
for(int j=a;j<=b;j++){
if(i+j>n){
e[i][]+=kp1;
e[i][]+=kp2;
e[i][]+=kp3;
break;
}
e[i][]+=(e[i+j][]+)*kp1*p2[i+j]+(e[i+j][]+)*kp1*p3[i+j];
e[i][]+=(e[i+j][]+)*kp2*p1[i+j]+(e[i+j][]+)*kp2*p3[i+j];
e[i][]+=(e[i+j][]+)*kp3*p1[i+j]+(e[i+j][]+)*kp3*p2[i+j]+(e[i+j][]+)*kp3*p3[i+j];
kp1*=(p0[i+j]+p1[i+j]);
kp2*=(p0[i+j]+p2[i+j]);
kp3*=(p0[i+j]);
} }
} int dcmp(double a,double b){
if(fabs(a-b)<=eps)return ;
return a>b?:-;
}
int main(){
int T;
scanf("%d",&T);
while(T--&&scanf("%d%d%d",&n,&a,&b)==){
for(int i=;i<=n;i++){
scanf("%lf%lf%lf%lf",p0+i,p1+i,p2+i,p3+i);
}
calc();
printf("%.8f\n",e[][]);
}
return ;
}