首页 > 代码库 > ZOJ 3329
ZOJ 3329
方程很明显有
d[i]=sum(pk*d[i+k])+p0*d[0];
其中pi可以在开始时枚举求出。
设d[i]=A[i]*d[0]+B[i],
代入上式
d[i]=(sum(pk*A[i+k])+p0)+sum(pk*B[i+k])+1
可得
A[i]=sum(pk*A[i+k])+p0
B[i]=sum(pk*B[i+k])+1
这种设系数方法好像挺常用挺经典的。在HDU 的MAZE也有用这种方法的。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;double A[600],B[600];double p[20];int main(){ int T; int n,k1,k2,k3,a,b,c; scanf("%d",&T); while(T--){ scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c); memset(p,0,sizeof(p)); double p0=1.0/(k1*k2*k3); for(int i=1;i<=k1;i++){ for(int j=1;j<=k2;j++){ for(int k=1;k<=k3;k++) if(i==a&&j==b&&k==c) continue; else p[i+j+k]+=p0; } } memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); for(int i=n;i>=0;i--){ A[i]=p0;B[i]=1; for(int j=1;j<=k1+k2+k3;j++){ A[i]+=p[j]*A[i+j]; B[i]+=p[j]*B[i+j]; } } printf("%.15lf\n",B[0]/(1-A[0])); } return 0;}
ZOJ 3329
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。