Hdu练习

Published: by Creative Commons Licence

  • Tags:

HDU1693

题意

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

题解

插头DP的入门题。类似于状态压缩动态规划,每个单元格可以填入六种图画,记$f(i,j,s)$表示为前i-1行放置好了,并放置好了第i行前j列,问从下往上看,能看到的m个单元格的状态为s,有多少种放置方案。

由于一个单元格只需要保存其是否与下侧单元格相连,如果相连,该列的状态为1,否则为0。这样就可以组成我们的状态。同时第i行j-1列单元格是否图画是否与右侧相连,相连记1,否则记0。这样我们需要维护的状态大小共m+1位,总状态数为$O(nm\cdot 2^{m+1})$。

HDU1150

题意

两台机器A、B,每台机器分别有n和m种模式。k个任务,每个任务可以被机器A以模式x或机器B以模式y处理。每次切换模式,都需要重启机器,问处理完所有任务最少需要重启多少次机器。

题解

很容易发现,这是一个二分图问题。一开始,能看出,如果我们以任务作为左边结点,而机器的状态作为右边结点,任务与机器状态的关联转换为边。问如何最少激活右边结点来使得通过网络的流量总共为k。

激活结点的问题看似可以用费用流来解决,比如每个状态与终点连一条边,边上每流量费用为1。但是实际上这个问题不是费用流问题,因为实际上只有第一个单位流的费用为1,后面的流式免费的。

实际上我们将最少激活数看做做少顶点选择数,将A机器的状态作为左边结点,将B机器的状态作为右边结点,每一个任务(i,x,y),建立一条从左边x结点到右边y结点的边。问题就是如何选择最少的顶点集合S,使得边的至少一个端点属于S,这是一个最小顶点覆盖问题,最小顶点覆盖数与最大匹配数是相等的,因此直接上KM算法即可。

HDU4035

题意

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

题解

由于给的图是一株树,因此有特殊的优化技巧,如果不是树,这数据量肯定过不了。

记f(i)表示从第i个结点出发到离开的期望步数。很显然:

下面说一下优化。挑选合适的$a_i$和$b_i$使得下面等式对所有i成立:

简化第一个等式可以得到:

那么可以得到$a_i$和$b_i$的递推公式

由于递推公式有环,因此还是不可解。这里我们注意到,我们可以将等式进一步处理,这里以$a_i$为例:

我们先处理叶子结点,之后逐层向上处理。很显然由于需要知道$a_{father(i)}$,每一个$a_i$都无法正常计算得到。但是当我们处理$a_{father(i)}$的时候,我们可以通过左移消除掉从孩子中带来的关于自己的部分,同时增加自己父亲的部分。而对于$a_1$,由于没有父亲,因此我们可以认为$a_{father(1)}=0$,代入就可以求出$a_1$。

对于b做同样处理即可。