1
12
2016
3

POJ3028 Shoot-out

http://poj.org/problem?id=3028

一眼迭代卡精度，然后发现牛仔是存在策略的_(:зゝ∠)_不能直接上。

n<=13，两眼状压DP，考虑dp[i][j][k]，i表示当前人的存活状况，j表示当前哪个人shoot，第k个人的存活期望概率。空间O(2^n*n*n)可以接受。初始化dp[1<<i][i][i]=1;dp[1<<i][i][j]=0;

Category: POJ | Tags: 状压dp

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com