2016-08-21

HDU 5819 Knights【概率dp】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5819

题意：

一条直线上有$0到n+1$个点，有$n$个骑士编号为$1到n$，编号为$i$的骑士在第$i$个点上。给定每个骑士初始方向，他们以相同速度前进，如果两个骑士相遇，每个骑士胜率为$50\%$，输的一方直接退出，最后剩下的一个骑士赢。问第$n$个骑士赢的概率。

分析：

首先必须观察出：

第N个骑士活到最后的情况就是他在往左走的过程中一路打败迎面走来的往右走的骑士。

那么就可以很自然的设计出状态$dp[i][j]:=前i个骑士有j个往右边走的概率$，最后答案就是$ \sum_{j=1}^{n-1}dp(n-1,j)\times(\frac{1}{2})^{j}$
对于位置$i$，分两种情况：

初始向右：显然有$dp[i][j] = dp[i-1][j-1]$
初始向左：设位置$i-1有k$个往右边走的骑士，那么位于位置$i$的骑士就必须打败$k-j$个骑士，然后再被打败。则有$$dp(i,j) = \sum_{k=j}^{i-1}dp(i-1,k)\times(\frac{1}{2})^{k-j+1}$$
优化一下就变为$\ dp(i,j)=dp(i,j+1)\times \frac{1}{2}+dp(i-1,j)\times \frac{1}{2}$
注意存在向左走的骑士打败左边所有骑士，然后走到左边尽头之后掉头变为向右走的情况，即$dp(i, 1)=\sum_{j=1}^{i-1}dp(i-1,j)\times(\frac{1}{2})^{j-1}$，同样可以优化为$dp(i,1)=dp(i-1,1)+dp(i,2)$

无脑的转移是$O(n^3)$的，观察式子的性质采用优化后的转移方程就为$O(n^2)$
一看见这种概率题大脑就非常混乱，无从下手，连最基本的性质都没观察出来。
还是不能慌，观察好性质，主要是设计好状态，基本就能做出来了。

代码：

/*************************************************************************
    > File Name: 5819.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/18 20:35:33
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5, mod = 1e9 + 7;
bool d[maxn];
ll dp[maxn][maxn];
ll pw[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	pw[1] = 500000004;
	for(int i = 2; i < maxn; i++){
		pw[i] = pw[i - 1] * pw[1] % mod;
	}
	for(int tt = 1; tt <= T; tt++){
		int n;scanf("%d", &n);
		for(int i = 1; i <= n; i++){
			scanf("%d", &d[i]);
		}
		if(n == 1){
			printf("Case #%d: 1\n", tt);
			continue;
		}
		memset(dp, 0, sizeof(dp));
		dp[1][1] = 1;
		for(int i = 2; i < n; i++){
			if(d[i]) dp[i][i] = dp[i - 1][i - 1];
			for(int j = i - 1; j >= 1; j--){
				if(d[i]) dp[i][j] = dp[i - 1][j - 1]; 
				else if(j == 1) dp[i][j] = (dp[i - 1][1] + dp[i][2]) % mod;
				else dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) * pw[1] % mod;
			}
		}
		ll ans = 0;
		for(int i = 1; i < n; i++){
			(ans += dp[n - 1][i] * pw[i] % mod) %= mod;
		}
		printf("Case #%d: %d\n", tt, ans);
	}
	return 0;
}