首页 > 代码库 > ZOJ 3329

ZOJ 3329

2024-08-03 02:25:04   219人阅读

方程很明显有

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


联系
我们