决策单调性：分治：2D/1D
决策单调性分治常见于 2D / 1D 动态规划，其中一维是 转移层数，且从一层 仅转移至下一层。
注意：下列讨论全部基于具有 决策单调性 的动态规划。
四边形不等式
通常情况下，决策单调性体现在其中的一维。
而另一位是层，假设当前要从上一层 \(f\)，转移到这一层 \(g\)。
即 \(i\) 的最小的最优决策点为 \(p_i\)。
满足决策单调性就要满足 \(\forall i<j,p_i\le p_j\)。
设 \(f_i=f_j+w(j,i)\) 那么 \(w\) 满足四边形不等式：包含劣于相交。
对于四边形不等式是否满足一般靠猜测。
我们 不证明 决策单调性，仅进行 猜测。
算法简介
一层一层 \(dp\)。
考虑暴力求出 \(mid\) 的最优决策点 \(p_{mid}\)。
由于相决策单调性，\(p_{1\sim mid-1}\le p_{mid}\) 和 \(p_{mid+1,n}>p_{mid}\)。
于是分治记四个参数 \(L,R,l,r\)，表示 \(\in [L,R]\) 的最优决策点还需要确定，最优决策点位于 \([l,r]\)。
每次分裂成 \([L,mid-1,l,p_{mid}]\) 和 \([mid+1,R,p_{mid},r]\) 即可。
时间复杂度转移一层 \(\mathcal{O}(n\log n)\)。
总时间复杂度 \(\mathcal{O}(k n\log n)\)。
技巧：贡献难算
有时我们无法直接计算两个位置之间的贡献，但若 \(l\to r\) 的权值能够快速地在 \(\mathcal{O}(v)\) 的时间内扩展到 \((l±1)→(r±1)\)，决策单调性仍然可以做到 \(\mathcal{O}(nv\log n)\)，即端点移动距离总和级别是线性对数。类比莫队，维护当前贡献区间的左右端点 \([l,r]\)，如果要查询某个区间的贡献，直接左右端点暴力跳到该区间。
例题 \(1\)：\(\text{CF868F}\)
给定一个序列 \(a\)，要把它分成 \(k\) 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。
\(\texttt{data range}\)：\(2 \leq n \leq 10^5\)，\(2 \leq k \leq min(n,20)\)，\(1 \leq a_i \leq n\) 。
\(dp_{i,j}\) 表示考虑到 \(a_i\) 分成了 \(j\) 个段，最小费用。
\(dp_{i,j}=\min\limits dp_{k,j-1}+cost (k+1,i)\)，\(cost\) 很显然满足四边形不等式，于是直接分治优化，由于费用无法直接算出，所以需要使用“技巧”。
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Mbe;
constexpr int N=100003,M=400003,inf=1ll<<60,mod=998244353;
char I[22000038],*J=I;
inline int read()
{
int x=0,y=1;
while(*J<48||57<*J){if(*J=='-') y=-1;J++;}
while(47<*J&&*J<58) x=(x<<1)+(x<<3)+(*J++^48);
return x*y;
}
int n,K,a[N];
int buc[N],js,f[N],g[N];
int L,R;
inline void ins(int pos){js+=buc[a[pos]],buc[a[pos]]++;}
inline void del(int pos){--buc[a[pos]],js-=buc[a[pos]];}
inline void calc(int l,int r)
{
while(L<l) del(L++);
while(L>l) ins(--L);
while(R<r) ins(++R);
while(R>r) del(R--);
}
inline void solve(int l,int r,int pl,int pr) //f->g
{
if(l>r) return;
int mid=l+r>>1,nr=min(pr,mid-1),p=-1;
g[mid]=inf;
for(int i=pl,v;i<=nr;i++)
{
calc(i+1,mid);
if((v=f[i]+js)<g[mid]) p=i,g[mid]=v;
}
solve(l,mid-1,pl,p),solve(mid+1,r,p,pr);
}
bool Med;
signed main()
{
fprintf(stderr,"%.4lf MB\n",(&Mbe-&Med)/1048576.0);
#ifdef Marsrayd
freopen("data.in","r",stdin);
freopen("zj.out","w",stdout);
#endif
fread(I,1,22000038,stdin);
n=read(),K=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) f[i]=f[i-1]+buc[a[i]],js+=buc[a[i]],buc[a[i]]++;
L=1,R=n;
for(int i=1;i<K;i++)
{
solve(1,n,0,n-1);
swap(f,g);
}
printf("%lld\n",f[n]);
return 0;
}
例题 \(2\)：\(\text{P5574}\)
给定 \(n,k\) 和长度为 \(n\) 的排列 \(a\)，你要将 \(a\) 划分成 \(k\) 段，最小化每一段的顺序对个数的和。
\(\text{data range}\)：\(n\le 25000,k\le 25\)。
\(dp_{i,j}\) 表示考虑到 \(a_i\) 分成了 \(j\) 个段，最小费用，然后直接树状数组 \(+\) 分治优化。
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Mbe;
constexpr int N=100003,M=400003,inf=1ll<<60,mod=998244353;
char I[22000038],*J=I;
inline int read()
{
int x=0,y=1;
while(*J<48||57<*J){if(*J=='-') y=-1;J++;}
while(47<*J&&*J<58) x=(x<<1)+(x<<3)+(*J++^48);
return x*y;
}
int n,K,a[N];
int tr[N],js,f[N],g[N];
int L,R;
inline int lowbit(int x){return x&-x;}
inline void upd(int x,int k){while(x<=n) tr[x]+=k,x+=lowbit(x);}
inline int ask(int x){int res=0;while(x) res+=tr[x],x-=lowbit(x);return res;}
inline void calc(int l,int r)
{
while(L<l) upd(a[L],-1),js-=ask(a[L]-1),L++;
while(L>l) --L,js+=ask(a[L]-1),upd(a[L],1);
while(R<r) ++R,js+=R-L-ask(a[R]),upd(a[R],1);
while(R>r) upd(a[R],-1),js-=R-L-ask(a[R]),R--;
}
inline void solve(int l,int r,int pl,int pr) //f->g
{
if(l>r) return;
int mid=l+r>>1,nr=min(pr,mid-1),p=-1;g[mid]=inf;
for(int i=pl,v;i<=nr;i++)
{
calc(i+1,mid);
if((v=f[i]+js)<g[mid]) p=i,g[mid]=v;
}
solve(l,mid-1,pl,p),solve(mid+1,r,p,pr);
}
bool Med;
signed main()
{
fprintf(stderr,"%.4lf MB\n",(&Mbe-&Med)/1048576.0);
#ifdef Marsrayd
freopen("data.in","r",stdin);
freopen("zj.out","w",stdout);
#endif
fread(I,1,22000038,stdin);
n=read(),K=read();
for(int i=1;i<=n;i++) a[i]=read();
reverse(a+1,a+n+1); //由于一开始看成逆序对了，这里 reverse 一下把顺序对变为逆序对。
for(int i=1,v;i<=n;i++) js+=(v=i-1-ask(a[i])),f[i]=f[i-1]+v,upd(a[i],1);
L=1,R=n;
for(int i=1;i<K;i++)
{
solve(1,n,0,n-1);
swap(f,g);
}
printf("%lld\n",f[n]);
return 0;
}
例题 \(3\)：\(\text{CF1603D}\)
斜率优化：1D/1D
算法简介
一类转移可以写成：\(f_i=\min/\max f_j+ cost _j+cost_i+F_iF_j\)（一些只与 \(i\) 有关的项，一些只与 \(j\) 有关的项，一个与 \(i,j\) 都有关的项）。
这样的转移一般可以斜优（将关于 \(j\) 的变成 \(x,y\)，关于 \(i\) 的变成 \(k,b\)）。
具体地，将方程改写为 \(f_j+cost_j=F_iF_j+f_i-cost_i\) 设 \(y=f_j+cost_j,k=F_i,b=f_i-cost_i\)），那么它就是一个一次函数表达式 \(y=kx+b\)，注意到 \(k\) 固定，所有的 \((x,y)\) 已知，由于 \(f_i=b+cost_i\)。所以要让 \(b\) 最大\(/\)小。
不妨设要求 $\min $，也就是说，给了你一堆点，斜率也固定，你要让 \(b\) 尽量小，所以维护一个下凸壳，让直线去切它就行。
- 如果满足插入的点 \(x\) 有序，\(k\) 有序可以单调队列/单调栈维护。
- 如果插入的只有 \(x\) 有序，需要在凸包上二分。
- 否则需要：\(\text{set}\) 维护动态凸包 \(/\) 李超树。
坑：
- 特判斜率不存在，记为 \(+\infty\) 或 \(-\infty\)。
例题 \(1\)：\(\text{P3195}\)
顺序排列着 \(n\) 条线段，每条长度为 \(C_i\)，你需要将这些线段划分成几组，一段放入一个容器，如果这一段包含从 \(i\) 到 \(j\) 的线段，容器长度为 \(x=j-i+\sum\limits_{k=i}^j C_k\)，费用为 \(w=(x-L)^2\)，其中 \(L\) 是给定常量，求最小的总费用可以装下所有线段。
\(\texttt{data range}\)：\(1\le n\le 5\times 10^4\)。
记 \(f_i\) 表示将前 \(i\) 个玩具装箱的最小费用，\(s_i=\sum\limits_{k=1}^i C_k+1\)。
\(f_i=\min f_j+(s_i-s_j+L)^2\)。
化简：\(\underline{f_j+s_j^2}_{\ y}=\underline{2(s_i-L)}_{\ k}\times\underline{s_j}_{\ x}+\underline{f_i-(s_i-L)^2}_{\ b}\)。
\(x\) 单调，\(k\) 单调，单调队列即可。
#include<bits/stdc++.h>
typedef long long LL;
typedef long double LD;
using namespace std;
bool Mbe;
constexpr int N=200003,M=400003,inf=0x3f3f3f3f,mod=998244353;
constexpr LD eps=1e-10;
char I[22000038],*J=I;
inline int read()
{
int x=0,y=1;
while(*J<48||57<*J){if(*J=='-') y=-1;J++;}
while(47<*J&&*J<58) x=(x<<1)+(x<<3)+(*J++^48);
return x*y;
}
int n,hh,tt,q[N];
LL L,s[N],dp[N];
inline short dcmp(double A,double B){if(fabs(A-B)<eps) return 0;return A<B?-1:1;}
LL sq(LL x){return x*x;}
LL X(int i){return s[i];}
LL Y(int i){return dp[i]+sq(s[i]);}
LL slope(int i,int j){return (LD)(Y(i)-Y(j))/(X(i)-X(j));}
bool Med;
signed main()
{
fprintf(stderr,"%.4lf MB\n",(&Mbe-&Med)/1048576.0);
#ifdef Marsrayd
freopen("data.in","r",stdin);
freopen("zj.out","w",stdout);
#endif
fread(I,1,22000038,stdin);
n=read(),L=read()+1;
for(int i=1;i<=n;i++) s[i]=read()+s[i-1]+1;
q[hh=tt=1]=0;
for(int i=1;i<=n;i++)
{
while(hh<tt&&dcmp(slope(q[hh],q[hh+1]),2*(s[i]-L))<0) ++hh;
int j=q[hh];dp[i]=dp[j]+sq(s[i]-s[j]-L);
while(hh<tt&&dcmp(slope(q[tt-1],q[tt]),slope(q[tt],i))>0) --tt;
q[++tt]=i;
}
printf("%lld\n",dp[n]);
return 0;
}
例题 \(2\)：\(\text{P5785}\)
\(n\) 个任务，每个有 \(t\) 和 \(c\) 两种属性，将 \(n\) 个任务划分为任意组，一组一组处理，处理一组的时候会产生额外的 \(s\) 时间（给定常量），一组的费用为结束时刻 \(\times\) \(\sum c\)，求最小总费用。
\(\texttt{data range}\)：\(1 \le n \le 3 \times 10^5\)，\(1 \le s \le 2^8\)，$ \left| T_i \right| \le 2^8$，\(0 \le C_i \le 2^8\)。
首先一个显然的状态是 \(f_{i,j}\) 表示前 \(i\) 个任务被分成了 \(j\) 组，最小总费用，为什么要记 \(j\) 呢，因为我们不知道前面有多少个 \(s\)，于是可以考虑，贡献先算技巧，在新划分成一组的时候，将 \(s\) 产生的对于后面的影响一起算了，加入答案，这样再划分一组的时候就不需要考虑前面分为了几组了，于是记 \(f_i\) 表示前 \(i\) 个任务已完成，所有的 \(s\) 的总贡献已经计算的最小总费用。
转移：记 \(d_i=\sum\limits_{j=1}^i t_j,g_i=\sum\limits_{j=1}^ic_j\)，\(f_i=\min\{ f_j +(d_i-d_j+s)(g_n-g_j)\}\)。
同时关于 \(i,j\) 的仅有 \(d_ig_j\) 考虑斜率优化。
化简完变为：\(\underline{f_j+d_jg_j-d_jg_n-g_js}_{\ y}=\underline{d_i}_{\ k}\times\underline{g_j}_{\ x}+\underline{f_i-d_ig_n}_{\ b}\)。
#include<bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N=5600003,M=400003,inf=0x3f3f3f3f,mod=998244353;
double eps=1e-9;
char I[22000038],*J=I;
inline int read()
{
int x=0,y=1;
while(*J<48||*J>57) if(*J++=='-') y=-1;
while(*J>=48&&*J<=57) x=(x<<1)+(x<<3)+(*J++^48);
return x*y;
}
int n,s;
int hh,tt,q[N];
double t[N],c[N];
inline short dcmp(double A,double B){return fabs(A-B)<eps?0:A<B?-1:1;}
double f[N],d[N],g[N];
inline double sq(double x){return x*x;}
inline double X(int i){return g[i];}
inline double Y(int i){return f[i]+d[i]*g[i]-d[i]*g[n]-g[i]*s;}
inline double slope(int i,int j){if(dcmp(X(i),X(j))==0) return Y(j)>=Y(j)?1e18:-1e18;return (Y(i)-Y(j))/(X(i)-X(j));}
inline bool check(int i,double k)
{
return dcmp(slope(q[i],q[i+1]),k)>0;
}
inline int find(double k)
{
if(hh==tt) return 1;
int l=1,r=tt,mid,res=r;
while(l<=r)
{
mid=l+r>>1;
if(check(mid,k)) r=mid-1,res=mid;
else l=mid+1;
}
return res;
}
bool Med;
signed main()
{
fprintf(stderr,"%.4lf MB\n",(&Mbe-&Med)/1048576.0);
#ifdef Marsrayd
freopen("data.in","r",stdin);
freopen("zj.out","w",stdout);
#endif
fread(I,1,22000038,stdin);
n=read(),s=read();
for(int i=1;i<=n;i++) t[i]=read(),c[i]=read();
for(int i=1;i<=n;i++) d[i]=d[i-1]+t[i],g[i]=g[i-1]+c[i];
//x 单调增，k 单调增。
q[hh=tt=1]=0;
for(int i=1,j;i<=n;i++)
{
j=q[find(d[i])],f[i]=f[j]+(d[i]-d[j]+s)*(g[n]-g[j]);
while(hh<tt&&dcmp(slope(q[tt-1],q[tt]),slope(q[tt],i))>0) --tt;
q[++tt]=i;
}
printf("%.0lf\n",f[n]);
return 0;
}
例题 \(3\)：\(\text{}\)
wqs 二分
wqs 二分优化常见于 2D / 1D 动态规划。其中一维是 选取物品个数。
对于限制某某某个数的题目可以想想 wqs 二分
算法详解
wqs 二分，全称王钦石二分，又称带权二分，斜率凸优化。常用决策单调性的一些 \(dp\) 优化方法一起使用。
该算法常见于限制选取物品个数的题目中，标志明显，所以看起来比较套路。设 \(f_i\) 表示最多（或最少、恰好）选取 \(i\) 个物品的答案，若 \(f\) 为凸函数可以 wqs 二分，凸函数的判断靠感觉。
\(nk\) 不行就是凸的。
举个例子：\(n\) 个数，最多分成 \(m\) 段，求每段的和的平方和的最小值。
- 暴力：\(n^2m\)。
- 决策单调性：\(nm\log n\)。
- 斜率优化：\(nm\)。
首先复杂度是肯定带 \(n\) 的，然而复杂度花在 \(m\) 上有点浪费，考虑在 \(m\) 上做手脚，记 \(dp_{i,j}\) 表示将 \(a_1\sim a_i\) 划分成 \(j\) 段的答案，记 \(f_i=dp_{n,i}\)，感性猜测 \(f\) 是凸的。
例题 \(1\)：
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(K\) 条白色边的生成树。
题目保证有解。
限定了白色边的边数，可以考虑 wqs 二分。
想要多选白色边就让白色边权值变小，想要少选就让白色边权值变大，二分变化的幅度即可。
标签：le,cost,int,mid,Part,单调,优化,dp From： https://www.cnblogs.com/Marsrayd/p/17008666.html