欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

决策单调性口胡

程序员文章站 2022-10-08 15:53:16
例题 定义一段序列的费用中相同元素的对数。求把给定序列a分为m段后各段费用总和的最小值,1 例题 四边形不等式 求证$w[b,d]+w[a,c]\le w[a,d]+w[b,c](a注意此处的$w[l,r]$是原方程中的$w[l+1,r]$,即表示的是子段$(l,r]$内相同元素的对数。考虑一种元素 ......

例题

定义一段序列的费用中相同元素的对数。求把给定序列a分为m段后各段费用总和的最小值,1<n<=1e5,m<=min(n,20)。——《cf868f》

例题-sol(fake)

设f[i,j]为把前i位置分为j段的最小费用和,转移\(f[i,j]=\min_{k\in[j-1,i)}f[k,j-1]+w[k+1,i]\),比较好的暴力实现可以做到o(n^2m),这仍是远远不够的。

决策单调性

若对于j1<j2<i1<i2满足i1的最优解转移自j1,那么存在i2的最优解转移自j1<j2<i1(另一种描述是对于a<b<c<d,若c从b转移比从a转移更优,则d从b转移比从a转移更优,显然这是完全等价的)。具有这样性质的方程存在一个十分优雅的最优决策序列:一个单调不降的序列。

决策单调性的判定

例如在\(f[i]=\min_{j\in[1,i)} f[j]+w[j,i]\)中,表示决策点调性的式子设为uexp,则
\[ \cases{f[b]+w[b,c]\le f[a]+w[a,c]\\ \mathbb{uexp}}\rightarrow f[b]+w[b,d]\le f[a]+w[a,d] \]
显然\(\mathbb{uexp}:w[b,d]+w[a,c]\le w[a,d]+w[b,c]\),这就是“四边形不等式”。

如何证明四边形不等式呢?

例题-四边形不等式

求证\(w[b,d]+w[a,c]\le w[a,d]+w[b,c](a<b<c<d)\)
注意此处的\(w[l,r]\)是原方程中的\(w[l+1,r]\),即表示的是子段\((l,r]\)内相同元素的对数。考虑一种元素\(e\),它在子段\((a,b]\)\((b,c]\)\((c,d]\)中分别出现了\(x\)\(y\)\(z\)次,那么他对于\(w\)的贡献满足
\[ w_e(b,d)+w_e(a,c)=\pmatrix{x+y\\2}+\pmatrix{y+z\\2}=\frac{x^2+2y^2+z^2+2xy+2yz-x-2y-z}2\\ w_e(a,d)+w_e(b,c)=\pmatrix{x+y+z\\2}+\pmatrix{y\\2}=\frac{x^2+2y^2+z^2+2xy+2yz+2xz-x-2y-z}2 \]
明晃晃的有上式小于等于下式了。这对所有的元素都成立,故整体也成立,证毕。

类似的我们简单推式子、归纳或者打表就能证明了。

决策单调性的应用

因此往往可以在转移过程中维护最优决策序列,每次转移时在序列里二分即可,前提为转移代价可快速计算。

另一种方法是分治整个需要转移的序列,同时划分对应的决策区间,显然这要求决策序列静态(即按阶离线转移)。可以处理\(w\)难算的情况。

例题-sol

显然此题可以很适合于分治法,不如先观察实现

inline void maintain(int x) {(use[x]^=1) ? sum+=cnt[a[x]]++: sum-=--cnt[a[x]];}
inline void maintain(int l,int r) {
    static int l=1,r=0;
    while(l>l) maintain(--l);
    while(l<l) maintain(l++);
    while(r>r) maintain(r--);
    while(r<r) maintain(++r);
}
void div(int j,int l,int r,int l,int r) {
    if(l>r) return;
    int mid=(l+r)>>1,bmid=l;
    for(int i=l; i<=min(mid,r); ++i) {
        maintain(i,mid);
        if(f[j][mid]>f[j-1][i-1]+sum) bmid=i,f[j][mid]=f[j-1][i-1]+sum;
    }
    div(j,l,mid-1,l,bmid);
    div(j,mid+1,r,bmid,r);
}
int main() {
    ...
    memset(f,inf,sizeof f); f[0][0]=0;
    for(int j=1; j<=m; ++j) div(j,1,n,1,n);
    ...
}

似乎很容易理解啊。就不细讲了

时间复杂度难在考察maintain的复杂度,如果我们在maintain中加入一句if(l=r+1) l=l,r=l-1;和不加的区别,这样可以把maintain整体上的过程分为两部分,复杂度都约是o(nlogn)的。

目的达成~

习题

给定长为n的序列w,和常数l、p,试求将分为若干段后,每段|w之和+段长-1-l|^p之和的最小值,输出一组方案。——《诗人小g》

令s[i]=s[i-1]+w[i]+1,转移方程 \(f[i]=\min_{j\in[0,i)}f[j]+|s[i]-s[j]-1+l|^p\)

四边形不等式就不证了,暴力拆几个拿来看。 总之这是满足决策单调性的。然后就能做了,似乎不好用分治,因为转移不离线。

数形结合理解决策单调性

\(j: g_j(i)=f[j]+|s[i]-s[j]-1+l|^p(j<i)\)

  1. i是递增的
  2. f[i]是不降的
  3. s[i]是上升的

顶点方程: s[i0]=s[j]+1-l

\(g_j(i)\)的顶点是\((s'[s[j]+1-l],s[j]+1-l)\)\(s'[s[i]]=i\)

任意\(j_1<j_2\)满足\(g_{j_1}(i)\)的顶点在\(g_{j_2}(i)\)的顶点的左下方。

因此旨在维护所有已经出现图形的底部及分割点。

没想到吧,这竟然是一篇讲义 2333。