HDU5346MZL'sgame(状态设计各种强)

真是太奇妙了&＃xff0c;感觉这是这个暑假写的最厉害的DP了&＃xff08;说的好像写过几道DP一样&＃xff09;&＃xff0c;设计的状态精妙。

 

因为题解不知道在说个毛线&＃xff0c;而且貌似写错了&＃xff0c;请问i-1的时候有j-1的活人为什么多攻击一次人会复活&＃xff1f;反正我没看懂。。而且下面还有情况接下来说。

把它翻译成人话。。

 

由于每个人等概率出于任意一个位置。不妨视为有序&＃xff0c;即从1-n一个一个选中人。该人死亡则跳过。最后统计出所有位置的情况即为一个人的存活率&＃xff08;这个题解说的好像比我容易懂&＃61; &＃61;&＃xff09;

 

设计的状态是

　　dp[i][j]表示&＃xff0c;选中第i个人时&＃xff0c;第i-n&＃xff08;即没有攻击过的人&＃xff09;已经收到了j次攻击&＃xff0c;注意是已经。

转移方程

　　dp[i][j] &＃61; dp[i-1][j]*(1-(1-p)^j)//i-1这个人在j次攻击中死亡的概率&＃xff0c;也就是第j次攻击不是由第i-1个人发出而是由他更前面的人发出&＃xff0c;则为选中i-1时&＃xff0c;它已经收到了j次攻击&＃xff0c;且在这j次攻击中死亡了&＃xff08;1-打j下都不死的概率&＃xff09;概率。相乘

　　　　　　　　&＃43; dp[i-1][j-1]*(1-p)^(j-1&＃xff09; //i-1个人在j-1次攻击中存活&＃xff0c;即第j次攻击由i-1发出。

以上 就覆盖了所有情况。用逆元处理一下p&＃61;x*inv(p)%MOD 

最后统计结果。

结果就是对于所有位置&＃xff0c;选中他们时遭遇了k次攻击&＃xff0c;且在k次攻击里都没有死掉。也就是sigma(i&＃61;1->n, dp[i][k]&＃xff09;*(1-p)^k&＃xff0c;最后/n,因为一个人等概率存在于任意一个位置

 

 

最后有一个很奇怪的疑问。。。

我。。因为草稿上。。没有写j-1&＃xff0c;所以不小心写成了dp[i-1][j-1]*(1-p)^j&＃xff0c;最后统计的时候没有*(1-p)^k。。居然也AC了。。

所以这个DP应该有别的理解方法&＃xff1f;我再想想&＃61; &＃61;会有大神路过解答吗&＃xff1f;

 

另外如何才能想出这么精妙的DP呢&＃xff1f;DP渣表示不解。。