学习笔记

该学习笔记为2026.2.23至2026.3.1在信友队集训所学算法的笔记，每种算法抽取一道题写题解。
由于是给自己看的题解，所以证明过程基本都略了，而且可能不太严谨，慎用。

1.决策单调性优化\(dp\) P4767 [IOI2000] 邮局 加强版

决策单调性优化大多数用于区间拆分或区间合并 但我貌似没有做过区间合并的？，定义\(w(l,r)\)代表\([l,r]\)这个区间的价值。

比较通用的式子（以下\(min\)均可换为\(max\)）：
区间拆分的转移式：\(f_i = min_{j=1}^{i}f_j+w(i+1,j)\)
区间合并的转移式：\(f_{i,j} = min_{k = i}^{j}f_{i,k}+f_{k,j}+w(i,j)\)
不一定是一维的，也可能是二维的。

我们定义\(p(i)\)为\(i\)的最优转移点，也即\(f_i = f_{p(i)}+w(i+1,p(i))\)，当\(i < j\)，有\(p(i) \leq p(j)\)时，这个\(dp\)有决策单调性。

那么什么情况下有决策单调性呢？
区间拆分的结论：
当满足\(\forall a \leq b \leq c \leq d w(a,c)+w(b,d) \leq w(a,d)+w(b,c)\)（叫做四边形不等式）时，\(f\)具有决策单调性。
证明略
区间合并的结论：
当满足\(\forall a \leq b \leq c \leq d w(b,c) \leq w(a,d)\)（叫做区间包含单调性）且满足四边形不等式时，\(f\)具有决策单调性。
依旧证明略
理论上来说要通过证明区间包含单调性和四边形不等式判断出来\(f\)具有决策单调性后，才能使用决策单调性优化\(dp\) ，但实际上我从来没证过

好咯，扯完了决策单调性是什么和为什么判断条件后，该扯一下怎么做它的用处了。
单调性，会让我们想到二分，那么在做具有决策单调性的\(dp\)时，我们其实可以在具有单调性的那一维二分，从而使复杂度由\(O(n^2)\)变为\(O(n log n)\)，或者由\(O(mn^2)\)变为\(O(mn log n)\)，从而降低复杂度。
看一道题。

---

开始讲题。

朴素\(dp\)

设\(f_{i,j}\)代表考虑到第\(i\)个村庄，已经放了\(j\)个邮局，且\(i\)上有邮局的最小距离。
那么答案就是\(f_{n,m}\)。

考虑优化

为了方便决策单调性，我们将\(i\)和\(j\)换一下，使状态变为\(f_{j,i}\)。
感性理解一下， 当\(i\)增大时，\(p(i)\)是跟着增大的，符合决策单调性，可以用决策单调性\(dp\)，\(w(l,r)\)肯定要把邮局放中间，随便算一下就好了。

决策单调性优化\(dp\)板子：

void DP(int a,int b,int l,int r,int pl,int pr){
    if(l > r) return;
    int pm = pl,mid = (l+r)/2;
    f[a][mid] = f[b][pm]+w(pm+1,mid);
    for(int i = pl;i <= pr;++ i)
        if(f[b][i]+w(i+1,mid) < f[a][mid])
            pm = i,f[a][mid] = f[b][pm]+w(pm+1,mid);
    DP(a,b,l,mid-1,pl,pm);DP(a,b,mid+1,r,pm,pr);
}

AC代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[3005];
int q[3005];

int f[305][3005];

int w(int l,int r){
    int v = (l+r+1)/2;
    if((r-l+1)%2) return (q[r]-q[v])-(q[v-1]-q[l-1]);
    else return (q[r]-q[v-1])-(q[v-1]-q[l-1]);
}

void DP(int a,int b,int l,int r,int pl,int pr){
    if(l > r) return;
    int pm = pl,mid = (l+r)/2;
    f[a][mid] = f[b][pm]+w(pm+1,mid);
    for(int i = pl;i <= pr;++ i)
        if(f[b][i]+w(i+1,mid) < f[a][mid])
            pm = i,f[a][mid] = f[b][pm]+w(pm+1,mid);
    DP(a,b,l,mid-1,pl,pm);DP(a,b,mid+1,r,pm,pr);
}

signed main(){

    cin >> n >> m;
    for(int i = 1;i <= n;++ i)
        cin >> a[i],q[i] = q[i-1]+a[i];

    memset(f,0x3f,sizeof(f));
    f[0][0] = 0;
    for(int i = 1;i <= m;++ i)//枚举dp第一维
        DP(i,i-1,1,n,0,n);

    cout << f[m][n];

    return 0;
    
}

习题

这些习题都大差不差，只是\(w\)的计算方式有变化。

1.P4360 [CEOI 2004] 锯木厂选址

其实貌似这个才是学决策单调性优化做的第一题，但这题比较简单，不需要枚举dp第一维的循环，于是没有将它当做模版来做。
这个的\(w\)很好算的，路程乘以重量即可。一个重量的前缀和，一个路程乘重量的前缀和就行。

//q1为重量的前缀和，q2为路程乘重量的前缀和
int w(int l,int r){
    return (q2[r]-q2[l-1])-(q1[r]-q1[l-1])*d[r];
}

2.CF868F Yet Another Minimization Problem

这个题的\(w\)从上次查询位置开始更改暴力左右端点即可，复杂度分析用了类似莫队的分析方式 ，反正我不会。

//ql，qr分别为上次的端点，qans是答案，qc是一个桶
int w(int l,int r){
	while(ql < l) qans -= --qc[a[ql++]];
	while(ql > l) qans += qc[a[--ql]]++;
	while(qr < r) qans += qc[a[++qr]]++;
	while(qr > r) qans -= --qc[a[qr--]];
	return qans;
}

3.P5574 [CmdOI2019] 任务分配问题

逆序对个数，和上一个一样，暴力改左右端点，用树状数组维护比某个数大或小的数有多少个即可。不贴代码。

4.CF1603D Ciel and Gondolas

\(w\)十分好写，一个矩阵的和除以\(2\)就行，预处理一个二维前缀和。不贴代码。

5.P4072 [SDOI2016] 征途

emmm，推个式子，其实不难推，我自己就推出来了。

\( \begin{aligned} vm^2 &= \frac{(x_1-\overline{x})^2+(x_2-\overline{x})^2+……+(x_m-\overline{x})^2}{m}m^2\\ &=((x_1-\overline{x})^2+(x_2-\overline{x})^2+……+(x_m-\overline{x})^2)m\\ &=(x_1^2-2x_1\overline{x}+\overline{x}^2+x_2^2-2x_2\overline{x}+\overline{x}^2+……+x_m^2-2x_m\overline{x}+\overline{x}^2)m\\ &=m(x_1^2+x_2^2+……+x_m^2)-2m\overline{x}(x_1+x_2+……+x_m)+m^2\overline{x}^2 \end{aligned} \)
\(\because \overline{x} = \frac{sum}{m}\)（\(sum\)为\(n\)段路的总长度）
\( \begin{aligned} \therefore vm^2&=m(x_1^2+x_2^2+……+x_m^2)-2m\frac{sum}{m}(x_1+x_2+……+x_m)+m^2(\frac{sum}{m})^2\\ &=m(x_1^2+x_2^2+……+x_n^2)-2sum(x_1+x_2+……+x_m)+sum^2\\ &=m(x_1^2+x_2^2+……+x_n^2)-2sum^2+sum^2\\ &=m(x_1^2+x_2^2+……+x_n^2)-sum^2 \end{aligned} \)

抛去不变的\(m\)和\(sum\)，维护一下前缀和然后求个平方就行。

2.线段树优化\(dp\) P8476 ⌈GLR-R3⌋ 惊蛰

这个好像没啥好说的，就是有什么区间加，区间求和之类的可以用线段树优化，减少时间。直接看题。

---

设\(f_{i,j}\)代表使得\(b_i = j\)的最小代价，\(f_{i,j} = min_{k \geq j} f_{i-1,k}+w(b[i],j)\)，复杂度过大，不可接受。(这个\(w\)约等于题目中的\(f\)，\(w(x,y)\)
可以发现，\(b_i\)的值一定是从\(a\)里面找出来的，所以第二维就可以通过离散化由\(V\)简化到\(n\)。那么\(f_{i,j}\)就变为了使得\(b_i = a_j\)的最小代价，这里\(a\)是离散化过后的。
看到\(min_{k \geq j}\)，我们可以给\(f_{i-1}\)做一个后缀\(min\)，再把\(w(j,i然后\)f_{i,j} = $