决策单调性小结

前言

学了这一块我才明白原来以前的 DP 都是过家家。。。

下面部分内容来自 《算法竞赛进阶指南》

定义

决策单调性

对于形如 $F[i]=\min\limits_{0\le j <i}{F[j]+val(j,i) }$ 的状态转移方程，记 $p[i]$ 表示令 $F[i]$ 取到最小值的 $j$ 的值，即 $p[i]$ 是 $F[i]$ 的最优决策。若 $p$ 在 $[1,n]$ 上单调不减，那么称 $F$ 具有决策单调性。

四边形不等式

设 $w(x,y)$ 为定义在整数集合上的二元函数。若对于定义域上的任意整数 $a,b,c,d$ 满足 $a\le b \le c \le d$ ，都有 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ ，那么称函数 $w$ 满足四边形不等式。（也简记为“交叉小于等于包含”）

关于区间包含的单调性

若对于 $∀a≤b≤c≤d$，$w[a,d]≥w[b,c]$（或对于 $∀a≤b≤c≤d，w[a,d]≤w[b,c]$）则称 $w$ 满足关于区间包含的单调性

定理

定理 A：四边形不等式的另一种定义。

$w(x,y)$ 是定义在整数集合上的一个二元函数，若 $\forall a<b$ ，都有 $w(a,b)+w(a+1,b+1)\le w(a+1,b)+w(a,b+1)$，那么函数 $w$ 满足四边形不等式。

证明：

对于 $a<c$ ，有 $w(a,c)+w(a+1,c+1)\le w(a+1,c)+w(a,c+1)$.

对于 $a+1<c$ ，有 $w(a+1,c)+w(a+2,c+1)\le w(a+2,c)+w(a+1,c+1)$.

两式相加，得： $w(a,c)+w(a+2,c+1)\le w(a+2,c)+w(a,c+1)$.

以此类推 $\forall a\le b\le c$ ，$w(a,c)+w(b,c+1)\le w(b,c)+w(a,c+1)$.

同理 $\forall a\le b\le c\le d$ ，$w(a,c)+w(b,d)\le w(a,d)+w(b,c)$.

证毕。

定理二：

对于方程 $F[i]=min{F[j]+val(j,i) }$ ，我们称 $val(j,i)$ 为附属函数。

若附属函数 $val$ 满足四边形不等式，那么 $F$ 有决策单调性。

证明：$\forall i \in [1,n],j\in [0,p[i]-1]$，

即 ： $j<p[i]<i$

由决策单调性定义可得： $F[p[i]]+val(p[i],i)\le F[j]+val(j,i)$ .

$\forall i’\in[i+1,n]$ ，即 $j<p[i]<i<i’$ .

由于 $val$ 满足四边形不等式，所以交叉小于等于包含可以得到：

$val(j,i)+val(p[i],i’)\le val(j,i’)+val(p[i],i)$

根据同变量同侧原则进行移项得：

$val(p[i],i’)-val(p[i],i)\le val(j,i’)-val(j,i)$.

与一开始的不等式相加得；

$F[p[i]]+val(p[i],i’)\le F[j]+val(j,i’)$.

根据此式，发现以 $p[i]$ 作为 $F[i’]$ 得决策会更优，即 $F[i’]$ 的最优决策不会比 $p[i]$ 更小，即 $p[i]$ 单调不降。所以 $F$ 有决策单调性。

证毕。

具体操作

$F[i]=min{F[j]+val(j,i) }$

看这种 1D1D 的方程，直接计算显然是 $O(n)$ 的。

一旦具有决策单调性，就可以把复杂度降成 $O(nlogn)$ 的。

一般有两种方案：

二分栈（单调队列）

有单调性的玩意自然是可以用单调数据结构处理啦

对于决策集合，如果对 $p$ 进行维护，在过程中的任意时刻，$p$ 一定是单调的。

于是我们每次一定可以找到一个位置，使得在这个位置之前的决策都比当前决策好，这个位置之后所有决策都更劣。

于是可以把这个位置之后的所有决策都变成当前决策。

于是我们发现这貌似是一个区间修改？

要用线段树或者树状数组嘛？

没有必要。

首先要明确，对于队列这种数据结构每次进队出队操作都要是 $O(1)$ 的，如果如果使用了线段树或者树状数组进行修改那会导致复杂度不正确，甚至本身就是不太可行的。

可以发现每次要修改的值都是一样的，所以考虑直接把他们看成一体。

具体地，我们可以建立一个队列，其中存放一些三元组。

三元组形如 $node(p,l,r)$ ，代表 $[l,r]$ 内的值都是 $p$ 。

于是我们的修改操作就变成了一整段一整段地修改。

于是对于每一个 $i\in[1,n]$ ，都进行以下操作：

  1. 检查队头：设队头为 $(p_0,l_0,r_0)$ ，若$r_0=i-1$，那么直接删队头。

$f[i]$ 的值必然已经求出来了，对于一个针对区间比 $i$ 更早的三元组，完全对我们来说是没有价值的。

  1. 取队头进行计算。

  2. 尝试加入新决策，依照以下步骤
    (1). 取出队尾 $node(p_t,l_t,r_t)$.

    (2) 若对于 $f[l_t]$ 来说，$i$ 是比 $j_t$ 更优的决策，即 $f[i]+w(i,l_t)\le f[j_t]+w(j_t,l_t)$，记 $pos=l_t$，删除队尾，返回步骤(1)。

    (3) 若对于 $f[r_t]$ 来说，$i$ 是比 $j_t$ 更优的决策，即 $f[j_t]+w(j_t,r_t)\le f[i]+w(i,r_t)$，去往步骤(5)。

    (4) 否则，则在 $[l_t,r_t]$ 上二分查找出位置 $pos$，在此之前决策比 $i$ 优，在此之后决策 $i$ 更优，将 $[l_t,r_t]$ 修改为 $[l_t,pos-1]$，去往步骤(5)。

    (5) 把三元组 $(i,pos,n)$ 插入队尾。

由于有二分所以时间复杂度 $O(nlogn)$ 。

代码片段：

inline int BIN(int loc,int x){
    int ans=q[loc].r+1,l=q[loc].l,r=q[loc].r;
    while(l<r){
        int mid=(l+r)>>1;
        if(calc(mid,q[loc].v)<=calc(mid,x))r=mid,ans=mid;
        else l=mid+1;
    }
    return ans;
}

inline void insert(ll i){
    q[tail].l=max(q[tail].l,i);
    while(head<tail&&calc(q[tail].l,i)>=calc(q[tail].l,q[tail].v))tail--;
    if(head>tail)q[++tail]=(node){i,i,n};
    else{
        int pos=BIN(tail,i);
        if(pos>n)return;
        q[tail].r=pos-1;
        q[++tail]=(node){i,pos,n};
    }
}

void solve(){
    head=1,tail=0;
    q[++tail]=(node){0,1,n};
    for(re int i=1;i<=n;i++){
        insert(i);
        if(head<tail&&q[head].r<i)head++;
        else q[head].l=i;
        p[i]=max(p[i],calc(i,q[head].v));
    }
}

分治

u1s1，这个比二分栈好写的多。

但是比较局限。

假设已知 $[l,r]$ 的最优决策在 $[kl,kr]$ 上。

再设 $f[mid]$ 的最优决策为 $p$

根据决策单调性的定义可知：

$f[l,mid-1]$ 的最优决策在 $[kl,kmid]$ 中

$f[mid+1,r]$ 的最优决策在 $[kmid,kr]$ 中

于是就可以分治了。

模板如下：

void solve(int l,int r,int kl,int kr){
    int mid=(l+r)>>1,kmid=kl;
    double MAX=0;
    for(re int i=kl;i<=min(mid,kr);i++){
        double tmp=a[i]+sqt[mid-i];
        if(tmp>MAX)MAX=tmp,kmid=i;
    }
    p[mid]=max(MAX,p[mid]);
    if(l<mid)solve(l,mid-1,kl,kmid);
    if(r>mid)solve(mid+1,r,kmid,kr);
}

时间复杂度同样是 $O(nlogn)$ 。

例题

这一块例题实在是太多，但是我实在是太弱，所以只能完成为数不多的几道。

CF868F Yet Another Minimization Problem && CF833B The Bakery

有一篇好题解

大伙全然把他当作双倍经验做就好了（虽然第二个有线段树优化 DP 的做法，但是今天不说（我也是学了决策单调性才知道原来这个题还能决策单调性做的））

题目出奇地类似：

将一个长度为 $n$ 的序列分为 $k$ 段，使得总价值最小(大）。

一段区间的价值表示为区间内x相同（不同）数字的个数。

一个区间内相同（不同）数字个数这是莫队的拿手好戏，可以先不考虑。

可以比较轻松地列出转移方程：

设 $f[i][j]$ 为把前 $i$ 个数分成 $j$ 段所需要的最大价值，可以得出： $f[i][j]=\max{f[i-1][j-1]+val(j+1,i)}$，其中 $val(l,r)$ 表示的是 $[l,r]$ 这个区间的价值。

可以看出，随着 $i$ 的增加，如果 $j$ 不变，显然 $f[i][j]$ 单调不降。所以， $f[i][j]$ 在向右转移时具有决策单调性。

然后套个板子就行了？

CF868F 代码：

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e5+5;
const int maxm=25;

ll n,k,kmid;

ll a[maxn];

ll f[maxn][maxm];

ll L=1,R=0,cnt[maxn],sum;

inline void add(ll x){
    sum+=cnt[x]++;
}

inline void del(ll x){
    sum-=--cnt[x];
}

inline ll val(ll l,ll r){
    while(L<l)del(a[L]),L++;
    while(L>l)L--,add(a[L]);
    while(R<r)R++,add(a[R]);
    while(R>r)del(a[R]),R--;
    return sum;
}

void solve(int l,int r,int kl,int kr,int now){
    int mid=(l+r)>>1,kmid=kl;
    for(re int i=kl;i<=min(mid,kr);i++){
        ll pre=f[i-1][now-1]+val(i,mid);
        pre<f[mid][now]?f[mid][now]=pre,kmid=i:0;
    }
    if(l<mid)solve(l,mid-1,kl,kmid,now);
    if(r>mid)solve(mid+1,r,kmid,kr,now);
}

template<typename T> 
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(n),read(k);
    for(re int i=1;i<=n;i++){
        read(a[i]);
    }

    memset(f,0x3f,sizeof(f));
    f[0][0]=0;

    for(re int i=1;i<=k;i++){
        solve(1,n,1,n,i);
    }

    printf("%lld\n",f[n][k]);


    return 0;
}

复杂度 $\text{O(nklogn)}$。

然后大家可以注意这玩意比线段树优化 DP 快了一半。

可见决策单调性是个好玩意。

P3515 [POI2011]Lightning Conductor

题目也很简单：给定一个长度为 $n$ 的序列 ${a_n}$，对于每个 $i\in [1,n] $，求出一个最小的非负整数 $p$ ，使得 $\forall j\in[1,n]$，都有 $a_j\le a_i+p-\sqrt{|i-j|}$

$1≤n≤5×10^5，0 \le a_i \le 10^9$

第一手资料往往是不好用的.

$a_j\le a_i+p_i-\sqrt{|i-j|}$

移项可以得到：

$p_i \ge a_j-a_i+\sqrt{|i-j|}$

$p_i=\max{a_j+\sqrt{|i-j|}}-a_i$

去掉绝对值：

$p_i=\max{\max{a_j+\sqrt{i-j}}(j\in[1,i]),\max {a_j+\sqrt{j-i}}(j\in[i+1,n])}-a_i$

发现前半部分具有决策单调性；

求解前半部分：即

$\max{\max{a_j+\sqrt{i-j}}(j\in[1,i]),\max {a_j+\sqrt{j-i}}(j\in[i+1,n])}$

两边分开做，另外一边直接序列翻转就可以了

然后两者取个最大值。

最后不要忘记减掉 $a[i]$

于是我们既可以单调队列也能分治。

这里一并给出

单调队列：

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e6+5;

ll n;

ll a[maxn];

struct node{
    ll v,l,r;
}q[maxn];

ll head=1,tail;

double p[maxn],sqt[maxn];

inline double calc(int i,int j){
    return a[j]+sqt[i-j];
}

inline int BIN(int loc,int x){
    int ans=q[loc].r+1,l=q[loc].l,r=q[loc].r;
    while(l<r){
        int mid=(l+r)>>1;
        if(calc(mid,q[loc].v)<=calc(mid,x))r=mid,ans=mid;
        else l=mid+1;
    }
    return ans;
}

inline void insert(ll i){
    q[tail].l=max(q[tail].l,i);
    while(head<tail&&calc(q[tail].l,i)>=calc(q[tail].l,q[tail].v))tail--;
    if(head>tail)q[++tail]=(node){i,i,n};
    else{
        int pos=BIN(tail,i);
        if(pos>n)return;
        q[tail].r=pos-1;
        q[++tail]=(node){i,pos,n};
    }
}

void solve(){
    head=1,tail=0;
    q[++tail]=(node){0,1,n};
    for(re int i=1;i<=n;i++){
        insert(i);
        if(head<tail&&q[head].r<i)head++;
        else q[head].l=i;
        p[i]=max(p[i],calc(i,q[head].v));
    }
}

inline void rev(){
    for(re int i=1;i<=n/2;i++){
        swap(a[i],a[n-i+1]);
        swap(p[i],p[n-i+1]);
    }
}

template<typename T> 
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(n);
    for(re int i=1;i<=n;i++){
        read(a[i]);
        sqt[i]=sqrt(i);
    }

    solve();

    rev();

    solve();

    for(re int i=n;i;i--){
        printf("%lld\n",(ll)ceil(p[i])-a[i]);
    }


    return 0;
}

分治：

//#define LawrenceSivan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define INF 0x3f3f3f3f
#define re register
const int maxn=1e6+5;

ll n;

ll a[maxn];

double sqt[maxn],p[maxn];

void solve(int l,int r,int kl,int kr){
    int mid=(l+r)>>1,kmid=kl;
    double MAX=0;
    for(re int j=kl;j<=min(mid,kr);j++){
        double tmp=a[j]+sqt[mid-j];
        if(tmp>MAX)MAX=tmp,kmid=j;
    }
    p[mid]=max(MAX,p[mid]);
    if(l<mid)solve(l,mid-1,kl,kmid);
    if(r>mid)solve(mid+1,r,kmid,kr);
}

inline void rev(){
    for(re int i=1;i<=n/2;i++){
        swap(a[i],a[n-i+1]);
        swap(p[i],p[n-i+1]);
    }
}

template<typename T> 
inline void read(T &x){
    x=0;T f=1;char ch=getchar();
    while (!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    x*=f;
}

int main() {
#ifdef LawrenceSivan
    freopen("aa.in", "r", stdin);
    freopen("aa.out", "w", stdout);
#endif
	read(n);
    for(re int i=1;i<=n;i++){
        read(a[i]);
        sqt[i]=sqrt(i);
    }

    solve(1,n,1,n);

    rev();

    solve(1,n,1,n);

    for(re int i=n;i;i--){
        printf("%lld\n",(ll)ceil(p[i])-a[i]);
    } 
    

    return 0;
}

不过单调队列那个交 SPOJ 就 WA 了，不太清楚什么原因，也许是写假了但是碰巧这个题数据比较水。

后面的例题待补充…