DP复习计划

  • [SCOI2009] 粉刷匠

    $f[i][j]$表示当前行前$i$个刷了$j$下的最优答案。

    行内暴力DP一下然后搞一个分组背包。

  • [JLOI2015] 骗我呢

    神奇转化+容斥 Link

  • [HNOI2007] 梦幻岛宝珠

    $f[i][j]$表示容量为$j \times 2^i$的最优答案,一层内背包然后层与层之间转移。

  • [CQOI2017]小Q的棋盘

    $g[i][j]$表示在$i$的子数内走$j$步然后回到$i$的方案,$f[i][j]$表示在$i$的子树中走$j$步不会来的方案。
    $$
    f[i][j+k+1]=f[son][j]+g[i][k]\\
    f[i][j+k+2]=g[son][j]+f[i][k]\\
    g[i][j+k+2]=g[son][j]+g[i][k]
    $$

    顺便膜ViXbob一秒AK还发现了我题解的漏洞。

  • [HAOI2010] 软件安装

    Tarjan以后树上DP即可。(我竟然忘记打Tarjan了。

  • [BZOJ4987] Tree

    显然??答案是一个大小为$k$的联通块边权和×2然后减去其直径。

    $f[i][j][0/1/2]$表示$i$的子数选了$j$个点,已经确定了$0/1/2$个直径的最小距离。

    如果为0,表示子树的边权和乘2。

    如果为1,表示边权和乘2减去i和子树内最远的点距离。

    然后合并直径。
    $$
    f[i][j+k][0] \leftarrow f[son][j][0]+f[i][k][0]+w(i,son) \cdot 2\\
    f[i][j+k][1] \leftarrow f[son][j][0]+f[i][k][1]+w(i,son) \cdot 2\\
    f[i][j+k][1] \leftarrow f[son][j][1]+f[i][k][0]+w(i,son) \\
    f[i][j+k][2] \leftarrow f[son][j][0]+f[i][k][2]+w(i,son) \cdot 2\\
    f[i][j+k][2] \leftarrow f[son][j][2]+f[i][k][0] +w(i,son) \cdot 2\\
    f[i][j+k][2] \leftarrow f[son][j][1] + f[i][k][1] + w(i,son)
    $$
    复杂度$O(n^2)$

  • [Lydsy1710月赛] 小A的树

    直接用bool数组不好算。

    记$f[i][j]$为$i$的子树中选择$j$个点的最多黑点数,$g[i][j]$为最少黑点树。

    如果$\forall_{i} g[i][j] \leq qry[y] \leq \forall_{i} f[i][j]$就是合法的。

    交上去发现MLE了。然后把同一个数组用了两遍就能卡进去了。

    (其实并不用卡。只是我数组开多了。

  • [Codeforces 815C] Karen and Supermarket

    $f[i][j][0/1]$表示$i$的子树中选了$j$个物品,$i$是否用优惠券的最优答案。
    $$
    f[i][j+k][1] \leftarrow f[son][j][1]+f[i][k][1]\\
    f[i][j+k][1] \leftarrow f[son][j][0]+f[i][k][1]\\
    f[i][j+k][0] \leftarrow f[son][j][0]+f[i][k][0]
    $$

  • [SDOI2016] 排列计数

    错排递推式
    $$
    f[0]=1,f[1]=0\\
    f[i]=(i-1)(f[i-2]+f[i-1])
    $$
    答案为$\binom{n}{m}\cdot f[n-m]$

  • [LOJ6217] 扑克牌

    题面很能迷惑人的题。

    对于任意牌$(x,y)$,如果$ax+ay\leq n$则$x$和$y$之间可以同时选择。

    然后直接背包,输出$f[n]$

$$
f[j]\leftarrow f[j-a_i]+b_i
$$

  • [HAOI2008] 木棍分割

    第一问二分。

    设$f[i][j]$表示分$i$段前$j$个数的方案(要反过来不然不好做
    $$
    f[i][j]=\sum_{k=pre[j]-1}^{j-1}f[i-1][k]
    $$
    第一维可以滚掉,第二位转移是一段区间,可以用前缀和优化掉。

    复杂度$O(nm)$

  • [Codeforces Round518Div1 A]

    $f[i][j][0]$表示前$i$个数,第$i$个数为$j$,$a[i] \leq a[i-1]$的方案数

    $f[i][j][1]$表示前$i$个数,$a[i] > a[i-1]$的方案数。

    (一),如果当前$a[i]$已知,则枚举上一个数是什么。
    $$
    pre < a[i] : f[i][a[i]][1] \leftarrow f[i-1][pre][0]+f[i-1][pre][1]\\
    pre = a[i] : f[i][a[i]][0] \leftarrow f[i-1][pre][0]+f[i-1][pre][1]\\
    pre > a[i] : f[i][a[i]][0] \leftarrow f[i-1][pre][0]
    $$
    (二),如果当前$a[i]$未知,枚举这个数是什么。
    $$
    f[i][now][1]\leftarrow \sum_{k=1}^{now-1}f[i-1][k][0]+f[i-1][k][1]\\
    f[i][now][0]\leftarrow \sum_{k=now+1}^{200} f[i-1][k][0]+f[i-1][now][1]+f[i-1][now][0]
    $$
    初始状态$f[0][0][0]=1$,最终答案为$\sum_{i=1}^{200} f[n][i][0]$,复杂度$O(n\times 200)$

  • [JLOI2012] 时间流逝

    期望DP+树上高斯消元,见Link

  • [Codeforces 980D] New Year and Arbitrary Arrangement

    $f[i][j]$表示有$i$个‘a’和$j$个’ab’子序列对答案的期望。

    转移为$f[i][j]=pb \times f[i][j+i] + pa \times f[i+1][j]$

    特殊情况$f[0][0]$的时候选择b就会有问题。

    但是因为在第一个a之前的所有b都是没有意义的,可以直接忽略,所以可以看成一开始就放了一个a,那么最终答案为$f[1][0]$。

    但是如果出现无穷多a然后b不够的情况,状态数为无限。

    对于$i+j\geq k$的情况,只要再有一个b就会满足要求,因为这个状态数无限,需要手算。

    对于公比绝对值小于1的无限项等比数列求和公式为$\frac{a1}{1-q}$
    $$
    \text{set}~~p_a = \frac{a}{a+b},p_b=\frac{b}{a+b}~~~~p_a=1-p_b\\
    f[i][j]=(i+j)p_b+(i+j+1)p_ap_b+(i+j+2)p_a^2p_b+…~~~~(1)\\
    f[i][j]p_a=(i+j)p_ap_b+(i+j+1)p_a^2p_b+(i+j+2)p_a^3p_b+…~~~~(2)\\
    (1)-(2):\\
    (1-p_a)f[i][j]=(i+j)p_b+p_b(p_a+p_a^2+p_a^3+…)\\
    f[i][j]p_b=(i+j)p_b+p_b\frac{pa}{pb}\\
    f[i][j]=i+j+\frac{p_a}{p_b}
    $$

  • [ZJOI2012] 波浪

    高维DP大力转移+卡常+卡精+卡空间。Link

  • [Luogu1410] 子序列

    好难的绿题啊qwq..

    其实求一个非升子序列的长度即可。

    如果长度大于2,一定无解。

    等于2,可以把它们放到两个序列里面,有解。

    等于1,一定有解。

  • [ZJOI 2008] 生日聚会

    $f[i][j][a][b]$表示前$i$个人,$j$个男生,后缀里面男生比女生最多多$a$,女生比男生最多多$b$的方案数。

  • [Luogu 1373] 小a和uim之大逃离

    $f[i][j][a][0/1]$表示状态,暴力dp

  • [Luogu 1220] 关路灯

    $f[i][j][0/1]$表示关了$j$个灯,在左边还是在右边。转移讨论一下。

  • [Luogu 1273] 有线电视网

    $f[i][j]$表示$i$子树里面选$j$个最大收益,树上背包。

  • [Luogu1070] 道路游戏

    暴力dp,$O(n^3)$就能A。$O(n^2)$可以单调队列。

  • [Luogu1415] 拆分数列

    正反dp一遍。

  • [Luogu 4918] 信仰收集

    $ab$最大只有50,设$f[i][j]$表示走到$i$,还剩$j$步的方案。topo排序后转移。

  • [SDOI 2010] 地精部落

    $f[i][j]$表示前$i$位,第一个数的范围是$[1\sim j]$的方案数。
    $$
    f[i][j]=f[i][j-1]+f[i-1][i-j]
    $$
    为什么是这样?

    考虑选$1\sim j$,方案是$f[i][j-1]$。

    选$j$,方案是$f[i-1][i-j]$,因为目的是让$1$后面都小于$j$,就是从$2$开始先升后降的方案。

    虽然没有算这个,但是他和$f[i-1][i-j]$等价(可以把$x$理解为$n-x+1$)。

  • [BZOJ 3126] Photo

    $f[i]$表示前$i$个,$i$必须选的最优方案

    $f[i]=f[j]+1$,$j \in [L, R]$

    这里的R是包含i的线段的最左点-1,L是i之前线段的最右段点。

    单调队列优化。

Leave a Reply

Your email address will not be published. Required fields are marked *