HDU 4711 Weather 概率DP

HDU 4711 Weather 概率DP

題意：有個人，他在某個區域待了n天，這個區域有m個地方，有w種天氣情況，先給出這個人行程的每天的天氣情況，然後給出 從第i個地方到第j個地方的概率，也可以自身到自身，然後給出 某個地方 是某種天氣的概率，問你 這個人最優可能的行程路線也就是每天待在哪個地方，

概率DP，求出哪些路線概率最大 再在其中取最小字典序的

假設方程 dp[i][j] 代表 第i天待在j城市，狀態轉移

dp[i][j] = max(dp[i][j],dp[i - 1][k] * mp[k][j] * pp[j][nnum[i]]);其中mp[i][j]代表由i地方到j地方的概率，pp[j][nnum[i]]代表j這個地方天氣為nnum[i]的概率，0

然後交了幾把發現一直WA，方程沒錯 覺得是精度問題，因為每次有比較大小的過程，而且乘了2000次，肯定會有誤差的，於是改用了long double，但是還是錯誤，最後還是沒做出，後來看題解 發現可以用對數來解決，這高中書白讀了....把mp[i][j] 跟pp[i][j]的 概率 取對數 log(mp[i][j]),log(pp[i][j])，這樣後面的狀態轉移方程 乘法就可以寫成加法了

dp[i][j] = max(dp[i][j],dp[i - 1][k] + mp[k][j] + pp[j][nnum[i]]);

然後又開始交，發現還是一直WA，因為 mp[i][j]是有可能為0的，意思是 第i個地方不可能到第j個地方，這裡要判斷一下把 ,若為0 則mp[i][j] = inf,當然 pp[i][j]也有可能為0，在這裡判斷為是否為0考慮精度問題，我是 判斷它是否小於eps， eps 我精確到了 1e-16次都不行，最後直接改成if(mp[i][j] == 0.00)反而就過了，暈死，坑點好多的題目，

int n,m,w;

int nnum[1000 + 55];

double dp[1000 + 55][100 + 55];

double mp[100 + 55][100 + 55];

double pp[100 + 55][100 + 55];

int father[1000 + 55][100 + 55];

void init() {
	memset(father,0,sizeof(father));
}

bool input() {
	while(cin>>n>>m>>w) {
		for(int i=1;i<=n;i++)
			cin>>nnum[i];
		for(int i=0;i>mp[i][j];
				if(mp[i][j] == 0.00)
					mp[i][j] = -10000000;
				else mp[i][j] = log(mp[i][j]);
			}
		for(int i=0;i>pp[i][j];
				if(mp[i][j] == 0.00)
					mp[i][j] = -10000000;
				else pp[i][j] = log(pp[i][j]);
			}
		return false;
	}
	return true;
}

void dfs(int now,int pos) {
	if(now == 1) {
		cout< p) {
			p = dp[n][j];
			s = j;
			//cout<>t;
	while(t--) {
		init();
		if(input())return 0;
		cal();
		output();
	}
	return 0;
}