主题

主题

 
   

关于概率DP中的sigma与min/max的笔记

一般概率DP,会套上一个sigma(pi*____)以及min/max{F____}之类的。有的时候min/max在外面,有的时候sigma在外面。

关于区分,且做笔记。

首先“sigma(pi___”这一部分是概率DP必有的。表示期望。这是随机事件。

而“min/max{F___”这一部分是普通DP均有的。这是钦定事件。

那么sigma(pi___与min/max{F___的相互嵌套,看钦定与随机事件发生先后即可。

举几个例子:

  • 1076: [SCOI2008]奖励关(BZOJ)

http://www.lydsy.com/JudgeOnline/problem.php?id=1076

设第i次抛出了k。prefix[x]为x的前驱。

假设我们对于抛出的物品是给定,是否选择也是给定的,那么我们不难得到这样一个方程:

设F[i][S]为剩余i轮,现在已经吃了S集合,接下来的最大值。

  • 现在我们不能钦定抛出来的是什么食物,由此方程将会变为:


最后输出F[k][0]。

(好像上面的式子应该用“属于”而不应该用“包含于”)

借此仔细分析一下方程。由于我们是先考虑“抛出物品”,再决定“是否选择”。由此sigma(pi___在前面,min/max{F___在后面。

  • 另一种思考

如果改为“吃或者不吃”是随机的,而“抛出哪一个”是已经确定了,那么方程将会变为:


  • 插一句

似乎概率DP一般不能记录已经决策过的最优值,而最好记录未决策过可能的最优值。

  • 1415: [Noi2005]聪聪和可可(BZOJ)

http://www.lydsy.com/JudgeOnline/problem.php?id=1415

我们假设next[i][j]表示聪聪在i可可在j时,聪聪下一步会去哪个点。可以n遍BFS求出。d[i]表示i的度数。

接下来令F[i][j]表示i捉到j的期望时间。初始状态F[i][i]=0。

那么我们可以得到方程:


最后输出F[x][y]即可。

由于是先聪聪钦定了往哪个点走,再可可随机走一个地方。由此min在前面,max在后面。

  • 另一种思考

如果先是可可随机走,之后再是聪聪钦定走,方程就要反过来了。

 
 
评论