c/c++语言开发共享决策单调性口胡

例题

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

例题-sol(fake)

设f[i,j]为把前i位置分为j段的最小费用和，转移(f[i,j]=min_{kin[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_{jin[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_{jin[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。