ZOJ 3329(One Person Game)

題意：同時搖三個色子，三個色子的面數分别為 k1 , k2 , k3 ，若搖的結果分别為 a , b, c  ; 則積分置零，否則累加積分( i + j + k)(搖色子的結果)。求從零開始搖，積分超過 n 需要搖色子次數的期望。

分析：一開始我真沒做出來，推出公式 變了些形 就直接用記憶化搜尋寫了一遍，結果一直 T ， 後來看了别人的題解才明白，這裡借鑒一下，

最初的轉移方程不難推， 設 dp[ i ] 表示目前積分為 i ,積分超過 n 的期望值 ，pk 為 搖色子得到 k 積分的機率 ，p0為搖色子積分歸零的機率

則   

  ，細看方程已經形成環了 ，一般是用高斯消元解決(  暫時不會(￣▽￣)"  ) ，不過

這題有比較巧的做法，這個方程每一項都與dp[ 0 ]有關，且 dp[ 0 ]正是我們要求的結果，所有我們設

  ,  帶入上式整理得：

則 

則 A[i] , B[i] 都可以逆推出來，求出A[0] ,B[0] 之後結果就有了！

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int N = 600;

double A[N],B[N];
double p[50];

int main()
{
	int T;
	scanf("%d",&T);
	int n,k1,k2,k3,a,b,c;
	while(T--)
	{
		scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
		double p0=1.0/(k1*k2*k3);
		memset(p,0,sizeof(p));
		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))
		  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 k=1;k<=k1+k2+k3;k++)
        	{
        		A[i]+=A[i+k]*p[k];
        		B[i]+=B[i+k]*p[k];
			}
		}
		printf("%.16lf\n",B[0]/(1-A[0]));
	}
	
	return 0;
}