7.30 dp&dp优化

1.数位dp

---

P2657 [SCOI2009] windy 数

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

---

一般而言，我们从高位往低位进行填数处理。

状态设计：当前数位，上一位，是否有前导零，是否顶满。

int dfs(int len,int pre, bool zero, bool flag){
	if(len == -1){
		return 1;
	}
	if(!flag && ~pre && dp[len][pre]){
		return dp[len][pre];
	}
	int up = flag ? a[len] : 9;
	int ans = 0;
	for(int i = 0; i <= up; i++){
		if(~pre && abs(i - pre) < 2){
			continue;
		}
		if(i == 0 && zero){
			ans += dfs(len - 1, -1, 1, flag && (i == up));
		}
		else{
			ans += dfs(len - 1, i, 0, flag && (i == up) );
		}
	}
	if(!flag && ~pre)
		dp[len][pre] = ans;
	return ans ;
}

---

---

P7961 [NOIP2021] 数列

给定整数 $n, m, k$，和一个长度为 $m + 1$ 的正整数数组 $v_0, v_1, \ldots, v_m$。

对于一个长度为 $n$，下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$，我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$。

当这样的序列 $\{a_i\}$ 满足整数 $S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 的二进制表示中 $1$ 的个数不超过 $k$ 时，我们认为 $\{a_i\}$ 是一个合法序列。

计算所有合法序列 $\{a_i\}$ 的权值和对 $998244353$ 取模的结果。

【数据范围】

对所有测试点保证 $1 \leq k \leq n \leq 30$，$0 \leq m \leq 100$，$1 \leq v_i < 998244353$。

---

注意到题目限制是：二进制表示中 $1$ 的个数不超过 $k$ 我们可以从下往上进行 dp。

$dp_{i,k,j,t}$ 表示前 $i$ 位，当前有 $k$ 个二进制位，还有 $j$ 个空，当前二进制的和是 $t$，当前所有情况的乘积的和是多少。

我们可以尝试进行状态转移，具体而言，我们可以尝试枚举当前位有多少个 $1$，系数是组合数。

考虑转移的时候我们只需要枚举第 $i+1$ 位被选择的个数即可转移。

转移方程，枚举被选择的个数 $p$，$delta$ 表示当前位是否是 $1$：

$dp_{i+1,j+p,k+delta,\left\lfloor\frac{l+p}{2}\right\rfloor}\gets dp_{i,j,k,l}\times C_{n-j}^p\times (a_{i+1})^p$

dp[0][0][0][0] = 1;
for(int i = 0 ; i <= m + 1 ; i ++)
{
    for(int j = 0 ; j <= n ; j ++)
    {
        for(int k = 0 ; k <= n ; k ++) 
        {
            for(int l = 0 ; l <= n ; l ++)
            {
                for(int p = 0 ; p <= n - j ; p ++)
                {
                    int delta = (l + p) % 2;
                    dp[i + 1][j + p][k + delta][(l + p) / 2] += dp[i][j][k][l] * C[n - j][p] % mod * mul[i + 1][p] % mod;
                    dp[i + 1][j + p][k + delta][(l + p) / 2] %= mod;
                }
            }
		}
    }
}
int ans = 0;
for(int i = 0; i <= kk; i++)
    for(int j= 0; j <= n; j++)
        if(__builtin_popcount(j) + i <= kk)
            ans = (ans + dp[m + 1][n][i][j]) % MOD;

---

---

CF55D Beautiful numbers

给定 $a, b \le 9 \times 10^{18}$，问：介于 $a,b$ 之间，数字 $x$ 满足可以被其自身非零的各个数位整除的 $x$ 有多少个。

---

相似的，我们尝试记录当前状态。

后效性：数位是否出现/整除关系/是否顶满

仅与 lcm 相关，搜出来简化状态

令 $dp_{i,j,k}$ 表示剩下$i$位需要规划，这前 $i$ 位模 $2520$ 的余数是 $j$，当前的前 $i$ 位数的最小公倍数是 $k$，满足这些条件的数字个数。

可以得到转移方程

$$dp_{i,j,k}=\sum dp_{i-1,(j\times 10 +x) \bmod 2520,\operatorname{lcm}(k,x)} 1\le x\le \text{最大数} $$

int dfs(int rest, int mod, int lcm, bool flag)
{
	if(rest == 0)return (mod % lcm == 0);
	if(!flag && dp[rest][mod][a[lcm]])return dp[rest][mod][a[lcm]];
	int maxx = flag ? num[rest] : 9;
	int res = 0;
	for(int i = 0; i <= maxx; i++)
		res += dfs(rest - 1, (mod * 10 + i) % 2520, lcm * i / __gcd(lcm, i), flag & (i == maxx));
	if(!flag)dp[rest][mod][a[lcm]] = res;
	return res;
}

---

2.状压dp

---

【BZOJ3812】主旋律

给定 $n$ 个点，然后 $m \le n^2$ 条有向边，问：有多少个边的子集，满足保留子集内的边，整张图形如强连通。

$n \le 15$

---

对于容斥的思考是直接的，考虑缩点之后的情况：dag，我们尝试减去是 dag 的情况。

我们尝试枚举缩点之后没有入度的一层连通块，但是我们并不能保证我们枚举到的一定是满的一层，我们只能保证枚举到的是一层的子集。

比如我们枚举一个集合，钦定这个集合是强连通的，然后不存在指向这个集合的边，会算重。

经典考虑：枚举多个强连通块：奇数带上 $-1$ 的系数，偶数带上 $1$ 的系数，

根据容斥的考虑：对于非法情况我们恰好会算到一次，做 dp。

令 $f_{S,0/1}$ 表示 $S$ 集合中的点构成了奇数/偶数个出度为 $1$ 的 SCC 的总方案。$dp_S$ 表示使 $S$ 集合中的点强联通的方案数。

转移：

$$f_{S,0}=\sum\limits_{s\subseteq S\And p\in s}f_{S-s,1}\times dp_s, f_{S,1}=\sum\limits_{s\subseteq S\And p\in s}f_{S-s,0}\times dp_s $$

建立一些辅助的数组：$w_s$表示 $s$ 集合中的点向全集 $S$ 中的点可以连多少边。

$$dp_S=2^{w_s}-\sum\limits_{s\subseteq S}(f_{S,1}-f_{S,0})\times2^{w_s} $$

---

---

【九省联考 2018】一双木棋

给两个矩阵，$10 \times 10$，两个人进行博弈，第一个人先手，选择填位置, 这个位置满足左边和上面的点都已经填上东西（或者在边界），第一个人的得分是填的格子的 $\sum a$，第二个人的得分是 $\sum b$，每个人的策略都是自己的得分减对面的得分最大，问最后填出来的情况。

---

注意到格子很小，而且当前状态取出来是一个倒三角的形式，即从上到下递减，我们可以选择状压其差分序列。

具体我们可以尝试维护长度为 $20$ 的 $0/1$ 序列，其中插入 $10$ 个 $1$，相邻 $1$ 之间的空隙作为差分数组的大小。

对于博弈的过程我们就是选择自己 - 对方最优的决策进行处理。

---

---

AGC016F - Games on DAG

给定 $n \le 15$ 然后 $m \le n^2$ 这是一个 dag，满足 $(u,v) u<v$

问：保留所有 $2m$ 个子集的边，此时若存在两个棋子分别在 $1,2$，每人可以选择一个棋子向下移动一步，不能移动的时输，先手胜的可能方案数。

---

一个直观的想法：如果尝试枚举所有状态在计算 SG 函数是方便处理这

个问题的，显然我们不能枚举方案再进行计算

考虑怎么计算保留边的方案数

一个角度：如果我们按照 SG 函数值进行分层再考虑层之间的连边

比如我们从小到大进行考虑每层的情况，

连边限制：同层之间不能有连边，层间：高层往低层都有连边

---

3.斜率优化

---

斜率优化基本形式

斜率优化以一下式子引入。

$f_i$ = $\min f_j + a_i \times b_j$。

$b_i$ 是否单调？

$a_i$ 是否单调？

直线与截距的理解？

（从几何意义的角度进行处理？）

---

[HNOI2008] 玩具装箱

一个长度为 $n$ 的序列，分成若干段，每段编号连续，$i$ 的长度为 $C_i$，

消耗代价为$(j-i+\sum\limits_{k=i}^jC_k-L)^2$，最小化费用。

$n \le 5 \times 10^4 , 1 \le L, C_i\le10^7$

---

稍微写一下 dp 方程，然后我们来优化：

$dp_i=min(dp_j+(S_i-S_j-1-L)^2)$

化简：$dp_i=S_i^2-2S_iL+dp_j+(S_j+L)^2-2S_iS_j$

---

---

[SDOI2013] 保护出题人

出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。

参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。

第一关，一只血量为$a_1$点的墦尸从距离房子$x_1$米处速接近，你们放置了攻击力为$y_1$点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为$a_2$点的僵尸，与后一只僵尸距离$d$米，从距离房$x_2$米处匀速接近，你们重新放置攻击力为$y_2$点/秒的植物；……；第$n$关，僵尸队列共有$n$只僵尸，相邻两只僵尸距离$d$米，排头僵尸血量为$a_n$点，排第二的 僵尸血量$a_{n-1}$，以此类推，排头僵尸从距离房子$x_n$米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为$y_n$点/秒的植物。

每只僵尸直线移动速度均为$1$米/秒，由于植物射击速度远大于僵尸移动速度，可忽略植物子弹在空中的时间。所有僵尸同时出现并接近，因此当一只僵尸死亡后，下一只僵尸立刻开始受到植物子弹的伤害。

游戏得分取决于你们放置的植物攻击力的总和$\sum \limits _{i=1} ^{n} y_i$，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。

作为SDOI2013的参赛选手，你们能保护出题人么？

$1\le n \le 10^5 ,1 \le d,x,a \le 10^{12}$ 。

---

对于每个 $i$，答案是 $ans_i=max(\dfrac{sum_i-sum_{j-1}}{x_i+(i-j)d})$，其中 $sum_i=\sum\limits_{j=1}^ia_j$。

可以斜率优化，因为答案的表达式可以看成 $(x_i+i\times d,sum_i),(j*d, sum_{j-1})$ 两点的斜率

发现对于每个 $i,(x_i+i\times d,sum_i)$ 是个定点

所以对于点 $(j*d, sum_{j-1})$ 维护一个下凸包，二分查找凸包中与定点相连斜率最大值，把每个 $i$ 的答案相加即可

---

4.李超线段树

---

$f_i=\min\{f_j+a_i*b_j\}$

考虑这个的另一个角度：视为这里有一个斜率为 $b_j$ 的直线，然后截距是 $f_j$ 然后在 $a_i$ 点询问若干条直线的最小值。

思想：值域线段树，然后对于线段树一个节点保留在 $mid$ 位置最小的线

段，注意到，由于是直线，所以一定只会往一边递归。

复杂度 $n \log n$，考虑如果要仅在一个值域区间加入当前线段可以用线段

树先找到加入区间，然后再进行递归加入。

给出一种很好的实现。

---

P5785 [SDOI2012] 任务安排

机器上有 $N$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $N$，因此序列的排列为

$1,2,3...N$。

这 $N$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，

这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。

在每批任务开始前，机器需要启动时间 $S$，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。

每个任务的费用是它的完成时刻乘以一个费用系数 $F_i$ 。请确定一个分组方案，使得总费用最小

---

尝试直接写这个 dp 的式子，具体的：

$$f_i=\min\limits_j(f_j+S(S_{T_n}-S_{T_j})+S_{T_i}\times (S_{T_i}-S_{T_j}) $$

然后考虑经典的斜率优化的拆分方式。

---

---

P2305 [NOI2014] 购票

给定一棵树 $n\le 2\times 10^5$，然后边有边权，每个点有三个参数 $p, q, l$。

一个点可以往其祖先走，直到走到 $1$ 号节点，走的代价为 $p\times len+q$ 要求 $len \le l$ 。

问：每个点的代价是多少。

---

首先介绍一种不用撤回，直接维护的方式：

考虑出栈序：即，当前元素离开的时候，加入这个元素，形成的序列，然后我们在外层开普通线段树，然后在内层开李超线段树。

考虑当前出栈序在一个元素 $x$ 以后的所有元素，你发现包含了其所有祖先，和 dfs 序在其后的节点，考虑正着 dfs 后缀存在元素总是其祖先，$l$ 的限制就是区间询问了。

第二种处理方式，外层对 dfs 序开线段树，考虑 dfs 的过程，我们可以

暴力撤回，复杂度同样是 $\log n^2$

---

5.四边形不等式

---

对于一个二元函数 $w(i, j)$ 若：满足对于任意 $a, b, c, d$ 有

$w(a, c) + w(b, d) < w(a, d) + w(b, c)$ 则称这个函数满足四边形不等式。

一般而言，记作包含大于跨越。

通常而言，我们只需要取 $a = i, b = i + 1, c = j, d = j + 1$ 进行验证。

满足四边形不等式的函数具有决策单调性，$f_* = f_j + w(j + 1, i)$ 的 dp。

即对于 $i$ 而言的最优决策满足以下形式 $p_i \le p_{i+1}$

具体处理：

1、二分栈，栈维护当前决策的形式。

具体实现过程是一个队列中存 $(l,r,p)$ 表示在之后的 $l r$ 区间取 $p$ 决策是最优的，对于最左边 x 求完 dp 值的时候，将 $x$ 放入决策队列，并找到相应位置，显然 $x > P_4$，从队尾一个一个弹出，将决策 P 队尾的 $l$ 端点与 $x$ 进行比较，若 $x$ 更优，则弹出，最后在剩下的一个区间中二分到 $x$ 可以更新的区间。

2、整体二分，然后二分每个节点的最优决策，比如求出来 $mid$ 的最优决策然后进行划分处理。

注意，在 $f$ 和 $f$ 之间的转移是不能用整体二分的！

注意，也可以尝试用打表的方式进行验证。

---

P1912 [NOI2009] 诗人小G

说：给定一个序列，然后划分成若干块，每一块的代价为 $|\sum\limits_ia_i-L-1|^P$，问最小代价划分成若干块。

$n\le 10^5,P\le 10$

---

感受得到这个转移函数是满足四边形不等式的，所以我们用二分栈进行

处理，因为是 $p$ 次方，所以不太能维护斜率优化的形式。

打表也可以说明满足决策单调性！

---

---

THUSC2022 D1T2 最大连续和

给定序列 $A,B$，长度为 $10^5$，然后值为$[-10^9,10^9]$，问：首先对于 $b_i$ 去换任意一个 $a_j$，再对 $a$ 求最大子段和，你需要最大化这个最大子段和。

---

对于每个右端点，令 $h_i$ 表示他的最优左端点的位置，那么 $h_i$是递增的。

一个简洁的证明：对于 $i$ 与 $i+1$，若 $h_i>h_{i+1}$，首先考虑 $[h_i,i]$，假设换了 $k1$ 个，$[h_i , i + 1]$ 换了 $k2$ 个，显然 $k1 \le k2$，此时对于从 $[h_i, i + 1]$ 扩展到其最优区间 $[h_{i+1}, i + 1]$ 有答案是增加的，而且如果 $k2$ 增大，一定是用 $b$ 的 $\le k2$ 的东西换的，此时对于 $[h_i,i]$，同样的扩展，显然答案也是增加的，于假设矛盾。

整体二分求解即可。

---

6.凸优化

---

若当前做的 dp 与分段次数有关，然后分段数与 dp 值有凸函数关系，可以尝试用凸优化进行处理。

考虑 wqs 二分的过程，本质上是给分段带权（每多分一段带 mid 的权值），然后求带权极值。

考虑怎么说明凸函数？

实用主义的角度：打表（这个很有用，直接可以验证出来是不是满足条

件的），感受（你真的可以感觉得出来他是不是凸的，不用说明。

一个方便的说明方式：验证是否存在四边形不等式。

---

P4983 忘情

$$\frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2} $$

我们定义一段序列的值为这个，其中 $n$ 为此序列的元素个数。

我们给定一段长度为 $n$ 的序列,现在要求将它分成 $m$ 段，要求每一段的值的总和最小，求出这个最小值。

---

先写出转移方程：

$$f_i=\min\limits_j(f_j+(S_i-S_j+1)^2)$$

感受到这个东西是下凸的，即，他的差分是递减的，画出来导数的图像。

因为我们只取整数下标，所以有可能导数是离散的。

如果涉及到的东西都是整数，那么只需要整数二分，否则需要实数二分。

---

---

P4383 [八省联考 2018] 林克卡特树

一棵树，你需要断掉 $k$ 条边，然后加上 $k$ 条为 $0$ 的边（要求也形如一棵树），然后问：你树的直径最大可能是多少。

$n, k \le 3 \times 10^5$

---

写朴素的树形 dp，可以描述为选择若干条链，然后拼接在一起，注意，还是要按照断边进行 dp，具体的：

$f_{x,y,z}$ 表示当前 $x$ 子树，断了 $y$ 条边，然后留下来的边向上度数是 $z$。

感受到他是上凸的，所以可以 wqs 二分，然后这个问题就解决了。

---

END.