CodeForces 398B 概率DP 記憶化搜索

CodeForces 398B 概率DP 記憶化搜索

有點似曾相識的感覺，記憶中上次那個跟這個相似的 我是用了 暴力搜索過掉的，今天這個肯定不行了，dp方程想了很久也沒有想出來，有點無從下手的感覺，最後還是嘗試了一下記憶化搜索，以dp[0][0]為邊界，dp[x][y]代表當前有x行y列沒有彩色的 瓷磚，搜索起來思路還是很清晰的，可惜最後那個 算期望公式給寫錯了，瞎了好久，做出以後看了一下別人的做法，確實有點難想到，把塗好的都放在右下角，這樣就只有四種情況了，瓷磚移動肯定是有影響的，後來理解了他們那意思是 劃分西線把瓷磚劃分到右下角去，這樣 狀態轉移 其實跟記憶化搜索的一模一樣了，想不到那個轉移，

int n,m;

int xx[20000 + 55],yy[20000 + 55];

double dp[2000 + 55][2000 + 55];

int cntx = 0,cnty = 0;

void init() {
	memset(xx,0,sizeof(xx));
	memset(yy,0,sizeof(yy));
	memset(dp,-1,sizeof(dp));
}

bool input() {
	while(cin>>n>>m) {
		cntx = cnty = n;
		for(int i=0;i -1.0 + eps)return dp[nowx][nowy];
	if(nowx == 0 && nowy == 0)return dp[nowx][nowy] = 0.00;
	double p = nowx * 1.0/n;
	double q = nowy * 1.0/n;
	double ans = 1.00;
	if(nowx != 0)ans += dfs(nowx - 1,nowy) * p * (1.0 - q);
	if(nowy != 0) ans += dfs(nowx,nowy - 1) * (1.0 - p) * q;
	if(nowx != 0 && nowy != 0)ans += dfs(nowx - 1,nowy - 1) * p * q;
	return dp[nowx][nowy] = ans/(1.00 - (1.0 - p) * (1.0 - q));
}

void cal() {
	double ans = dfs(cntx,cnty);
	printf(%.10lf
,ans);
}

void output() {

}

int main() {
	while(true) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}