【每日一题】DP 1

· · 个人记录

前言

考了两道 DP 原题，全都暴毙。。。

决定每天刷一些 DP 题并记录下来，题解详细程度根据难度不等。

P3354 [IOI2005]Riv 河流

7.19 树形 DP

一个自然的想法是设 f[u][i] 表示子树 u 中建 i 个伐木场的最小花费，但发现无法计算子树中点的花费。
由于子树中运上来的木料不好计算，而祖先点是确定的，可以用栈顺便记录，加上 n\le100，因此考虑增加一维表示 u 的祖先中第一个建伐木场的点是哪个，这样就知道 u 的木料运到了哪里，在 dfs 到 u 时算出点 u 的花费。
转移见代码

// f[u][i][j]: u的祖先中上一个建伐木场的是i，子树u中建j个的最小花费
// g: 辅助转移。转移时表示u建伐木场的最小花费（f为u不建的）
void dfs(int u) {
    stk[++tp] = u; // 栈中为u的祖先
    for(int v = head[u]; v; v = nxt[v]) {
        dis[v] = dis[u]+w[v];
        dfs(v);
        For(i,1,tp) rFor(j,m,0) { // m为题目中的k
            f[u][stk[i]][j] += f[v][stk[i]][0],
            g[u][stk[i]][j] += f[v][u][0];
            // 手动转移一次，否则For(l)取min时f[u][stk[i]][j]保存的还是前面几颗子树的值
            For(l,1,j) // 树上背包
                f[u][stk[i]][j] = min(f[u][stk[i]][j],f[u][stk[i]][j-l]+f[v][stk[i]][l]),
                g[u][stk[i]][j] = min(g[u][stk[i]][j],g[u][stk[i]][j-l]+f[v][u][l]);
                // u建伐木场则子树v只需运到u。注意此时的j中并不包括在u建的这一个
        }
    }
    For(i,1,tp) { // 计算点u的花费
        rFor(j,m,1)
            f[u][stk[i]][j] = min(f[u][stk[i]][j]+val[u]*(dis[u]-dis[stk[i]]),g[u][stk[i]][j-1]);
        f[u][stk[i]][0] += val[u]*(dis[u]-dis[stk[i]]);
    }
    --tp;
}

P3232 [HNOI2013]游走

7.20 期望 DP（做过）

考虑先算每个点的期望经过次数 f_i

f_1=\sum_{(1,j)r\in E,j\neq n}\frac{f_j}{deg_j}+1 f_i=\sum_{(i,j)\in E,j\neq n}\frac{f_j}{deg_j},\ 1<i<n

高斯消元（注意特判 n）
边 (u,v) 的期望经过次数为

[u\neq n]\frac{f_u}{deg_u}+[v\neq n]\frac{f_v}{deg_v}

贪心地标号

P3287 [SCOI2014]方伯伯的玉米田

7.22 DS 优化 DP

首先每次操作的右端点一定是 n（若不是，延长到 n 一定不劣）
设 f[i,j] 为第 i 个点拔高了 j 次的最长不降子序列。

f[i,j]=\max\{f[k,l]+1\},1\le k<i,h[k]+l\le h[i]+j,0\le l\le j

二维 BIT（拔高后的高度，拔高次数）优化。时间复杂度 O(nk\log a\log k)

P1453 城市环路

基环树 DP 7.25

先找环，以环上相邻的两点 p,q 分别为根，强制令根选/不选作两次《没有上司的舞会》。

P6064 [USACO05JAN]Naptime G

环形 DP 7.26

发现破环成链不好处理，那就强制令 n 睡/不睡 DP 两次。
注意初值、转移时的 0、答案

P1272 重建道路

树形 DP 7.31

设 f[i,j] 为子树 i 中保留 j 个点的最小数目（边 (u,fa[u]) 也要断），则初值 f[u,1]=deg[u]（u 的所有连边都断），转移 ,f[u,i]=\min\{f[u,i],f[u,i-j]+f[v,j]-2\}（-2 是因为边 (u,v) 分别在 u,v 处各断了一次，但现在不断了），答案 \min\{f[u,p]\}。

P3177 [HAOI2015]树上染色

树形 DP 8.1（做过）

按定义不好算点对之间的距离，考虑每条边的贡献，即它在多少个点对的路径上，只要知道子树中黑点数即可。
具体做法：ziidan Judge_Cheung

P4766 [CERC2014]Outer space invaders

区间 DP 8.2

发现外星人出现的时间对彼此有影响，考虑以时间 DP。
每个外星人都要打死，那么对于每一段时间 [l,r]，可以先选择存活时间包含在这一段的外星人中 d 最大的（设为 p）打死（因为这个外星人无法被“顺便”打死，一定要针对他开一枪），转移方程：f[l,r]=\min\{f[l,i-1]+d[p]+f[i+1,r]\},i\in[a_p,b_p]。
观察这个方程，存活时间跨过 i 的外星人都会被顺便消灭，在 f[l,i-1],f[i+1,r] 中不会被考虑，而不跨过的会被分别计算。
有点笛卡尔树 DP 的感觉。

P5299 [PKUWC2018]Slay the Spire*

期望 DP 8.3

发现 ans 乘了 \binom{2n}m，因此这是一道假期望，真计数

首先考虑如果抽出的 m 张牌确定了，如何选 k 张来造成最大伤害。由于强化牌上的数字大于 1，因此一张强化牌、一张伤害牌一定不劣于两张伤害牌，那么方案就是先尽可能打强化牌（但不超过 k-1 张），然后打最大的伤害牌。设 a_i 为第 i 张强化牌上的数字， b_i 为攻击牌，默认递减。

分开 DP 强化牌和伤害牌。设 f[i,j] 为前 i 张强化牌选 j 张且选第 i 张的乘积之和，g[i,j] 为攻击牌的和之和（有点拗口，即 \sum 一种方案的伤害和），则

f[i,j]=\sum_{l=1}^{i-1}f[l,j]+f[i-1,j-1]\times a_i g[i,j]=\sum_{l=1}^{i-1}g[l,j]+g[i-1,j-1]+b_i\times\binom{i-1}{j-1}

组合数的意义是在前 i-1 张牌中选 j-1 张的方案数，第 i 张牌可以和这些方案组成前 i 张牌中选 j 张的。前缀和优化至 O(n^2)。

计算答案，分抽的强化牌数量考虑。
若小于 k-1，那就枚举强化牌数量 i，所选的最后一张攻击牌 j，ans\gets ans+\sum_{l=i}^nf[l,i]\times g[j,k-i]\times\binom{n-j}{m-k}，组合数的意义是在 (j,n] 中抽 m-k 张攻击牌的方案（不能抽强化牌，而抽出的攻击牌必须不优于 j）
若大于等于 k-1，那就枚举所选的最后一张强化牌 i，攻击牌 j，ans\gets ans+f[i,k-1]\times b_j\times\binom{2n-i-j}{m-k}（抽出的牌不能优于 i,j）
注意边界。同样可以前缀和优化，时间复杂度 O(n^2)（瓶颈在于预处理）

CF908G New Year and Original Order*

数位 DP 8.3（博客是 8.4 写的，假装它是新的一天吧）

设 len 为 n 的长度。有一个 O(9len^3) 的暴力：设 f[i,j] 为数字 i 在排序后出现在第 j 位的方案数，那么答案为 \sum_{i=1}^9\sum_{j=1}^{len}f[i,j]\times10^{j-1}，但数位 DP 时要记录出现过 <i,=i 的数位个数。

有一个经典的优化方式：\sum_{i=0}^9i\times f[x=i]=\sum_{i=0}^9f[x\ge i]（原本 f[x=i] 的系数 i 转化为在 x\in[1,i] 中各算一次），本题也类似。
考虑转换每个数位排序后的贡献，即把 S(k) 表示成若干个 111\cdots111 的和，如 235=111+111+11+1+1（可以想象成竖式），不难发现排序后第 j 位的数贡献是 \sum_{k=1}^j10^{k-1}，而这个方案数只需要记录 \ge i 的数位个数，时间复杂度 O(9len^2)

const int N = 705, mod = 1e9+7;

int len,ans,d[N],f[10][N][N];

int dfs(int u,int pos,bool lim,int x) {
    if( !pos ) return !x;
    if( !lim && ~f[u][pos][x] ) return f[u][pos][x];
    int res = 0;
    for(int i = 0, up = lim?d[pos]:9; i <= up; ++i)
        res = (res + dfs(u,pos-1,lim&&i==up,x-(i>=u))) %mod;
    if( !lim ) f[u][pos][x] = res;
    return res;
}

signed main() {
    memset(f,0xff,sizeof f);
    For(i,1,9) for(int j = 1, k = 1; j <= len; ++j, k = (k*10ll+1)%mod)
        ans = (ans + (LL)dfs(i,len,1,j) * k) %mod;
}

AT2000 [AGC002F] Leftmost Ball*

计数类 DP 8.6

结论：合法序列的任意前缀中白球数 \ge 颜色数

考虑直接 DP 最终的颜色状态。设 f[i,j] 为放 i 个白球，j 种颜色所有球的方案数（i\ge j），转移时讨论序列从左到右的第一个合法位置放什么（为了避免算重。放白球/其他颜色的这个位置可能不同）：如果放白球，贡献为 f[i-1,j]；放其他颜色：(n-j+1)\times\binom{nk-(j-1)(k-1)-i-1}{k-2}\times f[i,j-1]（从剩余 n-j+1 中颜色中选一种，第一个球放在从左到右的第一个合法位置，k-2 个球放在其他 nk-(j-1)(k-1)-i-1 个空中）

P3648 [APIO2014]序列分割

斜率优化 DP 8.6

结论：一个切割方案的得分与顺序无关。
证明：假设切成了 a,b,c, 三块，则 a(b+c)+bc=(a+b)c+ab

采用贡献延迟计算的思想，设 f[i,j] 为前 j 个元素分 i 次的最大得分，s[i]=\sum_{j=1}^ia_j，则 f[i,j]=\max\{f[i-1,k]+s[k]\times(s[j]-s[k]\}，设 g[j]=f[i-1][j]，省略第一维，改写一下 g[j]-s[j]*s[j]=-s[i]\times s[j]+f[i]
发现这是一个可以斜率优化的式子，由于 s[i] 不降，因此只需用单调队列维护凸包。注意算斜率是特判 s[i]=s[j]

P3959 [NOIP2017 提高组] 宝藏

状压 DP 8.8

见【杂题】NOIp

P3943 星空

状压 DP 8.13

先进行异或差分，把区间修改转化成两点修改。
问题转化为有 2k 个 1，每次可以将间隔 b_i 的两点取反，问全部变为 0 的最小代价。

发现 k 很小，可以状压，剩余的问题就是如何计算转移的代价，bfs 预处理出取反每个间隔所需要的最小代价即可。

时间复杂度也许是 O(nm+2^{2k}k^2)

P1450 [HAOI2008]硬币购物

背包 8.17

一个显然的做法是每次跑多重背包，但显然过不去。发现每次仅有 d_i，即每种物品的数量不同，考虑仅做一次完全背包，询问时减掉不合法的方案。
假定只有一种物品，那么不合法的方案相当于体积为 m-c_1(d_1+1) 的完全背包添上 d_1+1 个 1 物品。对于多个物品的情况容斥即可。

P5664 [CSP-S2019] Emiya 家今天的饭

计数类 DP 8.20

简化题意：给定一个矩阵，每行选一个点（每个位置有 a_{i,j} 个点）要求全局至少选一个，每列选择的点数不能超过总选择点数的一半。

不考虑合法性的情况数为 (\prod_i((\sum_j a_{i,j})+1))-1。发现不合法的情况只有一列超过 \lfloor\frac2n\rfloor，考虑枚举这一列 DP。设 f[i,j,k] 为前 i 行，不合法列填了 j 个，其他列填了 k 的方案数。转移时讨论当前这行不填/填不合法列/填其他列。不合法的情况数为 \sum_{j>k}f[n][j][k]。复杂度 O(mn^3)。
事实上没必要知道 j,k 具体是多少，只要 j>k 即可。考虑把 DP 状态改为 f[i,j] 表示前 i 行不合法列比其他列多选了 j 个的方案数，状态数减少了一个 n。注意 j 可能为负，需要坐标偏移。

P1350 车的放置

计数类 DP 8.22

设 h[i] 为第 i 列高度，f[i,j] 为前 i 列放了 j 个的方案数，转移时讨论当前这列放/不放。

一个问题是直接算的话在高度突变的地方不好处理（只知道前面放了几行，但不知道是哪些行），倒着 DP 即可。

P5017 [NOIP2018 普及组] 摆渡车

线性 DP 8.25

多次 TP 警告

P2059 [JLOI2013]卡牌游戏

期望 DP 8.27

如果对 DP 有较深理解，这题就很简单，但我没有。。。

考虑 DP 的条件之一：子问题重叠性，而本题中 n 个人的游戏，踢出一个人后变为 n-1 个人，这提示我们倒推，之后就很好做了。

设 f[i,j] 为 i 个人的游戏，第 j 个人获胜的概率（庄家为第 1 个人），转移时枚举庄家抽到哪张牌即可由 i-1 个人的情况推出 i 个人的。