决策单调性学习笔记

决策单调性（Flush Hu ）

这有什么用？

这能优化dp。

决策单调性和斜率优化差不多。

需要细心发现决策之间的递变规律。

比如： $f[k][i]=max(f[k-1][j]+suan(j+1,i))$

决策单调性有两种做法：

1.二分栈(队列)：

决策二分栈（一种单调栈）来维护所有有用的决策，其中栈顶是当前最优决策。

2.分治：

然而二分栈有一个局限性，那就是必须能快速计算 $w[i][j]$ 。如果不能 $O(1)$ 算的话，在求临界值k的时候复杂度会严重退化。

既然转移过程是单调并且离线的，我们考虑分治。假设当前我们求解一段区间 $fl,r$ ,而所有 $fl,r$ 的最优决策点在 $[L,R]$ 之间。对于 $[l,r]$ 的中点 $mid$ ，我们可以暴力扫一遍 $L−mid$ ，找到它的最优决策点 $k$ 。因为决策单调，所以 $fl,mid−1$ 的决策落在 $[L,k]$ 上，而 $fmid+1,rf$ 的决策落在 $[k,R]$ 上，变成了两个规模减半的小问题。

3.四边形不等式优化 (一般不用):

利用 $dp[i][j-1]$ 的决策点<= $dp[i][j]$ 的<= $dp[i+1][j]$ 的。在求解 $dp[i][j]$ 的时候就可以缩小决策点范围，做到O(n^2 * d)，其中转移一次的复杂度为O(d)

例题：[POI2011]Lightning Conductor

题意：

已知一个长度为n的序列a1,a2,…,an。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j, aj < = ai + p – sqrt(abs(i-j))

题解：

$p_{i} \geq a_{j}-a_{i}+\sqrt{|i-j|}$

$p_{i}=\max\limits_{j=1}^{n}\left\{a_{j}+\sqrt{|i-j|}\right\}-a_{i}$

$p_{i}=\max(\max\limits_{j=1}^{i}\left\{a_{j}+\sqrt{i-j}\right\},\max\limits_{j=i+1}^{n}\left\{a_{j}+\sqrt{j-i}\right\})-a_{i}$

单独看前一部分: $\max\limits_{j=1}^{i}\left\{a_{j}+\sqrt{i-j}\right\}$

很明显是个要用决策单调性优化的式子。

对于每个 $j$ ，把 $a_j+\sqrt{i-j}$ 看成关于 $i$ 的函数 $f_j$ 。我们要做的就是在所有 $j\leq i$ 的函数中找到最值。

观察发现，真正有用的函数只有最上面那个！然而实际情况比这个稍复杂些。sqrt的增速是递减的，因此可能存在一个j比较小的函数，在某一时刻被j比较大的函数反超。我们大概需要维护这样的若干个函数：

我们用队列实现决策二分栈。按j从小到大依次维护这些函数。

显然，对于其中任意两个相邻的函数 $f_t,f_{t+1}$ ，它们都有一个临界值 $k_{t,t+1}$ 。显然序列中的 $k_{1,2},k_{2,3}...$ 也要严格递增。否则，如果 $k_{t,t+1}\ge k_{t+1,t+2}$ ，可以想象 $f_{t+1}$ 根本没有用。

先for一遍i，我们尝试着把 $f_i$ 加入队列。这时候为了保证k递增，设队尾决策为t，我们判断，如果 $k_{t-1,t}\ge k_{t,i}$ （此时会有 $f_t(k_{t-1,t})\le f_i(k_{t-1,t})$ ），那么t没用，出队。自己画下图就懂了。

该出去的都出去后，i就可以加入队尾了。这时候可以来求 $p_i$ 了。我们检查一下队首决策h，如果 $t_{h,h+1}\le i$ ，说明h的巅峰时刻已经过去，出队。最后队首就是所有函数中的最大值。

代码:

#include
using namespace std;
#define suan(i,j) a[j]+sq[i-j]
const int N=5e5+5;
int n,a[N],q[N],k[N];
double p[N],sq[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
int erfen(int x,int y)
{
    int l=y,r=k[x]?k[x]:n,mid,ret=r+1;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(suan(mid,x)<=suan(mid,y)){ret=mid,r=mid-1;}
        else l=mid+1;
    }
    return ret;
}
void work()
{
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&suan(k[r-1],q[r])<suan(k[r-1],i))r--;
        k[r]=erfen(q[r],i);
        q[++r]=i;
        while(l<r&&k[l]<=i)l++;
        p[i]=max(p[i],suan(i,q[l]));
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        sq[i]=sqrt(i);
    }
    work();
    for(int i=1;i<=n/2;i++)
    {
        swap(a[i],a[n-i+1]);
        swap(p[i],p[n-i+1]);
    }
    memset(k,0,sizeof(k));
    work();
    for(int i=n;i;--i)
        printf("%d\n",max((int)ceil(p[i])-a[i],0));
    return 0;
}

当然，分治也能做啊。

solve(l,r,L,R)表示f[l]~~f[r]的最优决策点在L~~R

令mid=（l+r）/2

O（n）扫一遍取到k[mid]

继续分治

solve（l,mid-1,L,k[mid])

solve (mid+1,r,k[mid],R)

代码：

#include
using namespace std;
const int N=5e5+5;
int a[N];
double f1[N],f2[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
void solve1(int l,int r,int L,int R)
{
    if(l>r)return;
    int mid=(l+r)/2,g=0;
    double tmp=0.0;
    f1[mid]=a[mid];
    for(int i=L;i<=min(R,mid);i++)
    {
        tmp=a[i]+sqrt(double(mid-i));
        if(tmp>f1[mid])
        {
            f1[mid]=tmp;
            g=i;
        }
    }
    if(g==0)g=mid;
    f1[mid]-=a[mid];
    solve1(l,mid-1,L,g); 
    solve1(mid+1,r,g,R);
}
void solve2(int l,int r,int L,int R)
{
    if(l>r)return;
    int mid=(l+r)/2,g=0;
    double tmp=0.0;
    f2[mid]=a[mid];
    for(int i=R;i>=max(mid,L);i--)
    {
        tmp=a[i]+sqrt(double(i-mid));
        if(tmp>f2[mid])
        {
            f2[mid]=tmp;
            g=i;
        }
    }
    if(g==0)g=mid;
    f2[mid]-=a[mid];
    solve2(l,mid-1,L,g);
    solve2(mid+1,r,g,R);
}
int main()
{
    int n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    solve1(1,n,1,n);
    solve2(1,n,1,n);
    for(int i=1;i<=n;i++)
    printf("%lld \n",(int)ceil(max(f1[i],f2[i])));
    return 0;
}

再看道题：Ciel and Gondolas

题意：

将n个人分成K段，每段的人两两之间产生代价，求最小代价和

题解：

这题有更优的做法，这里就不讲了，只讲决策单调性优化dp。

$f[k][i]=max(f[k-1][j]+suan(j+1,i))$

$suan(i,j)$ 其实就是前缀和

代码:

#include
using namespace std;
const int N=4040;
const int inf=0x3f3f3f3f;
int n,k,sum,s[N][N],K,dp[N][1000],q[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
inline int gao(int x,int y)
{
    return s[y][y]-s[y][x];
}
inline int suan(int x,int y)
{
    int l=y+1,r=n,res=n+1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(dp[x][k-1]+gao(x,mid)>=dp[y][k-1]+gao(y,mid))
        {
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return res;
}
int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(j<=i)
            {
                s[i][j]=read();
                sum+=s[i][j];
            }
            else read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)s[i][j]+=s[i-1][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)s[i][j]+=s[i][j-1];
    for(int i=0;i<=n;i++)dp[i][0]=inf;
    dp[0][0]=0;
    for(k=1;k<=K;k++)
    {
        int L=1,R=1;q[L]=0;
        for(int i=1,j;i<=n;i++)
        {
            while(L<R&&suan(q[L],q[L+1])<=i)L++;
            j=q[L];
            dp[i][k]=dp[j][k-1]+gao(j,i);
            while(L=suan(q[R],i))R--;
            q[++R]=i;
        }
    }
    printf("%d\n",dp[n][K]);
    return 0;
}

题目：[NOI2009]诗人小G

代码：

#include
#define suan(i,j) f[j]+qpow(abs(s[i]-s[j]-L))//计算函数值
using namespace std;
const int N=1e5+5;
int n,L,P,s[N],q[N],k[N],pr[N];
long double f[N];
char str[N][33];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
long double qpow(long double b)
{
    long double a=1;
    int k=P;
    while(k)
    {
        if(k%2==1)a=a*b;
        b=b*b;
        k=k/2;
    }
    return a;
}
int erfen(int x,int y)
{
    int l=x,r=n+1,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(suan(mid,x)>=suan(mid,y))r=mid;
        else l=mid+1;
    }
    return r;
}
int main()
{
    int T=read();
    while(T--)
    {
        n=read();L=read()+1;P=read();
        for(int i=1;i<=n;i++)
        {
            scanf("%s",str[i]);
            s[i]=s[i-1]+strlen(str[i])+1;
        }
        int l=1,r=1;
        q[1]=0;
        for(int i=1;i<=n;i++)
        {
            while(l<r&&k[l]<=i)l++;
            f[i]=suan(i,q[l]);
            pr[i]=q[l];
            while(l=erfen(q[r],i))r--;
            k[r]=erfen(q[r],i);
            q[++r]=i;
        }
        if(f[n]>1e18)puts("Too hard to arrange");
        else{
            printf("%.0Lf\n",f[n]);
            q[r=0]=n;
            for(int i=n;i;q[++r]=i=pr[i]);
            for(;r;--r)
            {
                int i;
                for(i=q[r]+1;i<q[r-1];i++)
                    printf("%s ",str[i]);
                puts(str[i]);
            }
        }
        puts("--------------------");
    }
    return 0;
}

其他题目暂时咕咕