决策单调性口胡

例题

定义一段序列的费用中相同元素的对数。求把给定序列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。