WTommy’s BLOG

由于一直忙着写paper，做实验，也没有时间练习了～
赶上一次Topcoder SRM 384，就凑巧做了做，果然失败了，赛后做了做总结，记录一下！

250分题目：
很简单的一个题目，基本所有人都做对了，除非把题目读错的（我开始是没注意doc是要唯一的）。这题就不多说了！

500分题目：
一个很不错的状态压缩DP，之所以有点难度，因为他状态转移方程的特殊性。
简单回顾一下题目：
设有n个小朋友围成一个圈玩球，顺时针编号0到n-1。他们按顺时针的顺序轮流拿球去打其他人，每次轮到某人打击时，他都会选择另一个人去打，对于第i个人打中的概率是给出的，记为pro[i]%。一个人打完以后，不管打中没打中都要把球传给顺时针的下个人，被打中的人要离开这个游戏。这个游戏直到只剩下一个人终止，请问这个游戏期望要打多少轮才能结束？
题目中有个重要的提示是：所有的小朋友并不在乎自己在这个游戏中能存活多长时间，而是很想快速的结束这个游戏，可见他们选择打谁是有目的的。

题目的数据范围很小，n最大只有6，所以很容易想到用状态压缩DP。
即用dp[1<<n][i]表示状态，dp[mask][i]表示还剩下mask状态人时，该第i给人打，期望还会继续多少轮终止游戏。

很容易的列出状态转移方程：

dp[mask][i] = 1 + (min{ dp[mask^(1<<hit)][(i+1)%n] }*pro[i] + dp[mask][(i+1)%n]*(100-pro[i])) / 100.0   --> 其中hit是枚举被打的人

很多人（比赛时的我），都会想整个DP过程枚举的顺序可能会有问题，dp[mask][i]和dp[mask][(i+1)%n]是循环制约的，也许要解方程。

其实因为我们用mask作为阶段，那么dp[mask^(1<<hit)][?]都是已经求过的了，那么就可以很容易的把转移方程转化成：
在某一个特定的mask下：

dp[mask][i] = c * dp[mask][(i+1)%n] + f             (*)

注： |c| <= 1 并且 f是常数，是因为mask^(1<<hit)一定比mask小，所以是计算过的。

那么很容易证明这个方程(*)是收敛的，那么我们可以采用雅可比或者高斯-塞德尔迭代法求解，整个题目就解决了。