省选-动态规划-决策单调性 · Zhl2010 第二博客

四边形不等式

在成本函数 $w(j, i)$ 中，若对于任意 $a \le b \le c \le d$ 均有

w(a, d) + w(b, c) \ge w(a, c) + w(b, d)

则称函数 $w$ 四边形不等式。简单描述为：交叉小于包含。

Min 函数的四边形不等式： $w(a, d) + w(b, c) \ge w(a, c) + w(b, d)$ 。交叉小于包含。

Max 函数的四边形不等式： $w(a, d) + w(b, c) \ge w(a, c) + w(b, d)$ 。交叉大于包含。

等价形式

在满足四边形不等式的函数 $w$ 中，对于任意 $j < i$ 均有

w(j, i+1) + w(j+1, i) \le w(j, i) + w(j+1, i+1)

注意，这也符合交叉小于等于包含。也就是这个形式：

w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)

Min 函数的： $w(j, i) - w(j, i-1) \le w(j-1, i) - w(j-1, i-1)$ 。

Max 函数的： $w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)$ 。

证明

以求 $\max$ 为例，对于转移方程：

$f_i=\max f_j + w(j,i)$

如果满足：

w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)

如果在 $i-1$ 处 $j$ 比 $j-1$ 优，那么在 $i$ 处 $j$ 仍然比 $j-1$ 优。

因为：

f_{j-1}+w(j-1,i-1)\le f_j+w(j,i-1)

所以减去上式仍然成立：

f_{j-1}+w(j-1,i)\le f_j+w(j,i)

w(a, d) + w(b, c) \ge w(a, c) + w(b, d)

证明

若函数 $w$ 满足四边形不等式，则最优化问题

dp[i] = \min_{0 \le j < i} \{ dp[j] + w(j, i) \}

满足决策单调性，即最优决策点 $p[i]$ 满足 $p[i] \le p[i+1]$ 。

证明：对于任意 $j_2 < opt_{i_1}$ 且 $opt_{i_1}, j_2$ 为候选决策点，由最优性均有

dp[opt_{i_1}] + w(opt_{i_1}, i) \le dp[j_2] + w(j_2, i) \quad \text{（若 $ opt_{i_1} $ 优于 $ j_2 $ 时成立）}

同时，对于任意 $i_1 < i_2$ ，由四边形不等式可得

w(opt_{i_1}, i_2) + w(j_2, i_1) \ge w(opt_{i_1}, i_1) + w(j_2, i_2)

移项得

w(j_2, i_1) - w(j_2, i_2) \ge w(opt_{i_1}, i_1) - w(opt_{i_1}, i_2)

将上述两个不等式（最优性条件与四边形不等式导出式）相加，经过整理可推出

dp[opt_{i_1}] + w(opt_{i_1}, i_2) \le dp[j_2] + w(j_2, i_2)

即 $opt_{i_1}$ 对 $i_2$ 依然不劣于 $j_2$ ，从而决策点随 $i$ 增大单调不减，得证。

写法

分治

对于每个 $i$ ，保证转移的 $p$ 是单调的。

这种写法需要保证可以不按照 $1,2,\cdots,n$ 的顺序算，一般是二维 dp 的优化方法。

我们设 $solve(l,r,pl,pr)$ 表示 $l$ 到 $r$ 这个区间中决策点在 $pl$ 到 $pr$ 之间。

C++

void solve(int a,int b,int l,int r){
	if(a>b)return;
	int mid=a+b>>1;
	int id=l;
	for(int i=l+1;i<=min(mid-1,r);i++){
		if(h[id]+cost(id,mid)<h[i]+cost(i,mid))id=i;
	}
	f[mid]=max(f[mid],h[id]+cost(id,mid));
	solve(a,mid-1,l,id),solve(mid+1,b,id,r);
}

队列

我们对于 $[1,n]$ 维护决策点。设 $(p,l,r)$ 表示 $[l,r]$ 的最优决策点为 $p$ ，然后把若干个这样的三元组放进队列。

我们对于当前的 $i$ 可以直接从队列中队头获取到当前的最优的答案，然后考虑把 $i$ 加进去。

设队尾是 $(p,l,r)$ ：

如果到了 $r$ 处（ $r$ 可能到了 $n$ ） $i$ 都没有 $p$ 优， $i$ 就没用了。
如果在 $l$ 处 $p$ 都没有 $i$ 优， $(p,l,r)$ 就没用了。
否则二分出一个 $mid$ 保证 $[l,mid]$ 中 $p$ 更优， $[mid+1,r]$ 中 $i$ 更优。

最后插入 $(i,mid+1,n)$ 。

C++


void insert(int x){
	while(x<=q[r].l&&l<=r&&h[q[r].p]+cost(q[r].p,q[r].l<=h[x]+cost(x,q[r].l)))r--;
	if(l>r){
		q[++r]={x,1,n};
		return;
	}
	int L=max(q[r].l,x),R=q[r].r;
	while(L<R){
		int mid=L+R+1>>1;
		if(h[q[r].p]+cost(q[r].p,mid)<=h[x]+cost(x,mid))R=mid-1;
		else L=mid;
	}
	q[r].r=L;//注意，调了我 30 分钟 
	q[++r]={x,L+1,n};
}



void solve(){
	l=1,r=0;
	q[++r]={1,1,n};
	for(int i=1;i<=n;i++){
		while(q[l].r<i&&l<=r)l++;
		int p=q[l].p;
		f[i]=max(f[i],h[p]+cost(p,i));
		insert(i);
	}
	
}

P3515 [POI 2011] Lightning Conductor

P3515 [POI 2011] Lightning Conductor。

很好的板子题，两种写法都可以用。

$f_i = \max \{h_j+\sqrt{|i-j|}\}-h_i$

$w(j,i)=\sqrt{|j-i|}$

这个不好看，我们可以正反各做一次，去掉绝对值。

然后我们看 Max 的决策单调性： $w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)$ 。

求个导（其实感性理解一下就行了），这个显然符合的。

CF833B The Bakery

CF833B The Bakery。

这就是我前面说的，二维 dp 很多时候可以用分治写。

$f_{i,j}=f_{k,j-1} + cost(k+1,i)$

$w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)$ 。

P10538 [APIO2024] 星际列车

P10538 [APIO2024] 星际列车。

设 $f_i$ 表示到达第 $i$ 条边，只考虑结束时间 $<a_i$ 的饭：

$f_i=c_i+\min \{f_j+w(b_j+1,a_i-1)\}$

回想 $\min$ 中的决策单调性： $w(j, i) - w(j, i-1) \le w(j-1, i) - w(j-1, i-1)$ 。

在本题中，这个显然是成立的，感性理解一下就行了。

cost

计算方法

我们发现我们需要计算 $(l,r)$ 包含了多少个完整区间。用主席树，将饭依次插入，然后第 $i$ 个版本表示插入了所有 $r\le i$ 的饭，查询的时候只需要查询有多少个 $l\le i$ 。

注意需要离散化。

注意：求 $\le$ 需要 $upper\_bound-1$ ，如果 $lower_bound$ 会在没有的情况下 $>r$ 。

太难调了！！！

P5574 [CmdOI2019] 任务分配问题

P5574 [CmdOI2019] 任务分配问题。

决策单调性。

思路

$f_{i,j}$ 表示把前 $i$ 个数分成 $j$ 段的最小代价。

$f_{i,j}=\min_{k=1}^{i-1}f_{j-1,k}+cost(k,i)$

我们发现这个过不了，需要优化。

然后可以发现，这有决策单调性，于是就解决了。

这个决策单调性的写法不错，直接分治递归下去。

P4767 [IOI 2000] 邮局加强版

P4767 [IOI 2000] 邮局加强版。

$f_{i,j}$ 表示前 $i$ 个村庄放 $j$ 个邮局前 $i$ 个村庄的最小距离和， $w(i,j)$ 表示 $[i,j]$ 之间放一个的最小距离和。

f_{i,j}=\min\{f_{k,j-1}+w(k+1,i)\}

然后 $w$ 满足： $w(j, i) - w(j, i-1) \le w(j-1, i) - w(j-1, i-1)$ ，具有决策单调性。

决策点 $p_{i,j-1}\le p_{i,j}\le p_{i+1,j}$ 。可以看做每个维度都有决策单调性。

$w$ 的计算方法：w[l][r]=w[l][r-1]+x[r]-x[(l+r)/2];。因为其他村庄到中位数的距离变化总和恰好为 $0$ （中位数移动时，左侧和右侧的距离增减相互抵消）。

P5504 [JSOI2011] 柠檬

P5504 [JSOI2011] 柠檬。

$f_i = \max \{f_j + cost(i,j)\}$

$cost(i,j)$ 是这里面最大的 $s\times t^2$ 。我们可以优化一下表达，用 $i$ 和 $j$ 表示： $col_i\times(sum_i-sum_j+1)^2$ ，需要保证 $col_i=col_j$ 。

我们需要判断是否满足： $w(j, i) - w(j, i-1) \ge w(j-1, i) - w(j-1, i-1)$ 。我们发现相反，所以...决策点单调不增？

这道题的决策点单调不增是建立在已经用过的点之上的，新加入的点不算。

我们应该怎么写？越往后的决策点，只会在前几个点被选择，此后就不优了，这让我们想到了单调栈。

但是注意，每一个点都有能做决策的区间，还是需要二分判断这个点还有没有用。

我想到了一个不需要二分的写法，但是不知道哪里错了

反正决策点会在中间有一些错误，就是中间好像有一些多余的点。

DS 的解释：在单调栈中，我们需要保证栈中相邻决策点的临界位置是严格递增的，这样整个栈就形成了一个“凸壳”，查询时只需根据当前 s[i] 找到第一个临界位置大于 s[i] 的决策点，它就是最优的。

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100010],sum[100010],f[100010],cnt[100010];
vector<int>st[100010];
int cost(int i,int j){
	int tot=sum[j]-sum[i]+1;
    return a[j]*tot*tot;
}
int F(int x,int i){
	return f[(x-1)<0?0:x-1]+cost(x,i);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)sum[i]=++cnt[a[i]];
//	for(int i=1;i<=100000;i++)st[i].push_back(0);
    for(int i=1;i<=n;i++){
	    int c=a[i];
	    while(st[c].size()>=2){
	    	if(F(st[c][st[c].size()-2],i)>=F(st[c].back(),i))st[c].pop_back();
	    	else break;
		}
		st[c].push_back(i);
	    while(st[c].size()>=2){
	    	if(F(st[c][st[c].size()-2],i)>=F(st[c].back(),i))st[c].pop_back();
	    	else break;
		}
		int p=0;
        if(st[c].empty())p=i;
        else p=st[c].back();
		f[i]=max(F(p,i),F(i,i));
//		cout<<i<<' '<<p<<endl;
//		if(i==100)cout<<st[c][5]<<endl;
//		if(i==100)cout<<"---"<<F(5,100)<<' '<<F(47,100)<<' '<<F(39,100)<<endl;
//		if(i==5)cout<<"---"<<F(1,5)<<' '<<F(5,5)<<endl;
		
	}
    cout<<f[n]<<'\n';
    return 0;
}

只找到这一个错误：

C++

while(st[c].size()>=2){
	    	if(F(st[c][st[c].size()-2],i)>=F(st[c].back(),i))st[c].pop_back();
	    	else break;
		}
		st[c].push_back(i);
	    while(st[c].size()>=2){
	    	if(F(st[c][st[c].size()-2],i)>=F(st[c].back(),i))st[c].pop_back();
	    	else break;
		}