动态规划：决策单调性优化 dp

· · 算法·理论

1. 引入

决策单调性类似于斜率优化，说人话就是，在 dp 的时候，对着 i 做个 opt_i 的决策，那么随着 i 的增大，opt_i 肯定不会变小。一般情况可以用分治或者二分 + 队列来处理。

这个东西，我们不太好直接讲，因此，我们用几个题目来引入。

我们以 P3515 [POI 2011] Lightning Conductor 这道题来作为引入。

提取一下题目的关键信息，注意到说，对于一栋固定的建筑 i，转换一下式子，有 h_j-h_i+\sqrt{i-j}\le p，那么题目要我们求解的就是 h_j+\sqrt{i-j} 的最大值，因为 -h_i 是一个定值。

考虑转换一下视角，我们可以把 h_j+\sqrt{i-j} 看作一个关于 i 的函数，那么，那么对于一个问题，我们要求的其实就是这些函数在 x=i 时的最大的 y。

注意到从左往右和从右往左是镜像的，因此只需要正着处理一次，倒着处理一次即可。现在就是考虑如何处理的问题。

画图可以感受到，对于两个函数 f_x=h_x+\sqrt{i-x}，f_y=h_y+\sqrt{i-y}，默认 x<y，若存在一个 p，在对于 i<p 的时候 f_x>f_y，在 i=p 的时候 f_x=f_y，在 i>p 的时候 f_x<f_y，那么随着 i 的增大，f_x 一定没有反超的机会。

考虑简单的证明一下，做差即可，有 D=f_y-f_x=h_y+\sqrt{i-y}-h_x-\sqrt{i-x}=h_y-h_x+\sqrt{i-y}-\sqrt{i-x}，其中 h_y-h_x 是常数，对其求导，有

\boxed{ D'(i)=\frac{1}{2\sqrt{i-y}}-\frac{1}{2\sqrt{i-x}} }

考虑到说这个的 D(i) 显然是单调递增的，那么也就可以说明最初的单调性也是成立的。

那么就不难想到说，对于一个在当前是最优的函数 f_x，应该去找一个在 k 处反超 f_x 的函数 f_y。不难想到，可以二分。

具体的，我们考虑去枚举一个函数 f_y(x<y)，然后二分他与 f_x 的交点，记录 pos_y 表示函数 y 第一次成为最优的时间（相对于 f_x）而言，然后从这些 pos_y 中找一个最小的作为新的最优值，然后重复上述操作。这样的话就可以在 \cal O(n^2 \log n) 的时间复杂度内处理出来答案，当然还要反着处理一遍。

考虑优化，貌似可以用单调队列进行优化。

具体的，我们用一个 q 表示当前可行的方案，以 pos 的大小进行入队，其中，pos 越小的越靠近队首。

那么我们在外层枚举 i 的时候，也就可以顺便处理当前队列的答案，然后也可以入队处理。这样的时间复杂度就是 \cal O(n \log n) 的了。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int MAXN=5e5+10;

ll n,h[MAXN],tmp[MAXN],q[MAXN],pos[MAXN];
ll L[MAXN],R[MAXN];
namespace yixing{
    inline bool better(int j,int k,int x){
        ld x1=(ld)h[j]+sqrtl(x-j);
        ld x2=(ld)h[k]+sqrtl(x-k);
        return x2>=x1;
    }
    inline int cross(int j,int k){
        if (!better(j,k,n))return n+1;
        int l=k,r=n,res=l;
        while (l<=r){
            int mid=(l+r)>>1;
            if (better(j,k,mid))r=mid-1,res=mid;
            else l=mid+1;
        }
        return res;
    }
    inline void work(ll *ans){
        int head=1,tail=0;
        for (int i=1;i<=n;i++){
            while (head<=tail){
                int p=cross(q[tail],i);
                if (p<=pos[tail])tail--;
                else break;
            }
            if (head>tail){
                head=tail=1;
                q[1]=pos[1]=i;
            }else {
                int p=cross(q[tail],i);
                if (p<=n)q[++tail]=i,pos[tail]=p;
            }
            while (head<tail&&pos[head+1]<=i)head++;
            int j=q[head];
            ans[i]=h[j]+ceil(sqrt(i-j));
        }
    }
    inline void Main(){
        cin>>n;
        for (int i=1;i<=n;i++)cin>>h[i];
        work(L);
        reverse(h+1,h+1+n);
        work(tmp);
        for (int i=1;i<=n;i++)R[i]=tmp[n-i+1];
        reverse(h+1,h+1+n);
        for (int i=1;i<=n;i++)cout<<max(L[i],R[i])-h[i]<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}

:::

这种写法固然可以，甚至于说可以比较好的和后面的 wqs 二分结合，但是分治的写法仍然比较重要。

考虑 F_i=\max_{j<i}\{h_j+\sqrt{i-j}\}，单调性是已经证明过了的，也就是说，对于一段 i\in [l,r]，它所对应的 j 是在一个范围内的 [L,R]，然后取这个范围里的中点 mid，那么我们就可以把这个范围给划分成 [L,mid]，[mid,R]，然后分支下去做即可。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int MAXN=5e5+10;
const ll INF=4e18;
int n,h[MAXN];
ll L[MAXN],R[MAXN];
namespace yixing{
    inline void solve(int l,int r,int L,int R,ll *ans){
        if (l>r)return;
        int mid=(l+r)>>1,pos=-1;
        ld mx=-INF;
        for (int j=L;j<=min(mid,R);j++){
            ld val=(ld)h[j]+sqrtl(mid-j);
            if (val>mx)mx=(ld)h[j]+sqrtl(mid-j),pos=j;
        }
        ans[mid]=h[pos]+ceil(sqrtl((ld)mid-pos));
        solve(l,mid-1,L,pos,ans);
        solve(mid+1,r,pos,R,ans);
    }
    inline void Main(){
        cin>>n;
        for (int i=1;i<=n;i++)cin>>h[i];
        solve(1,n,1,n,L);
        reverse(h+1,h+1+n);
        solve(1,n,1,n,R);
        reverse(h+1,h+1+n),reverse(R+1,R+1+n);
        for (int i=1;i<=n;i++)cout<<max(L[i],R[i])-h[i]<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}

:::

2. 四边形不等式

然后考虑这道题 P4767 [IOI 2000] 邮局 加强版。

还是先考虑暴力嘛，不难想到说，我们可以去确定那些村庄要建立邮局，具体的，我们令 dp_{i,k} 表示从 1\sim i 最后一个邮局建在 i，然后总共建立了 k 个邮局的距离和的最小值。

那么自然有 dp_{i,k}=\min_{j<i} \{dp_{j,k-1}+w(j,i)\}。其他的先不说，先考虑这个 w(l,r) 如何求解。

比较显然，对于区间 [l,r]，由于两头都是有邮局的，那么肯定是取中间值的一个过程，具体的，我们找到了 a_{mid} 之后，对于当前是否是奇数进行分类讨论一下，然后处理一下前缀和，那么左侧就是 (mid-(l+1)+1)\times a_{mid}-(s_{mid}-s_l)=(mid-l)\times a_{mid}-(s_{mid}-s_l)，右侧就是 ((r-1)-(mid+1)+1)\times a_r -(s_{r-1}-s_{mid})=(r-1-mid)\times a_r-(s_r-s_{mid})，简单处理一下即可，如下：

:::info[Code]

for (int j=1;j<=n;j++){
    int mid=j;
    for (int i=j+1;i<=n;i++){
        while (mid+1<i&&2*a[mid+1]<=a[j]+a[i])mid++;
        ll L=(s[mid]-s[j])-1ll*(mid-j)*a[j];
        ll R=1ll*(i-mid-1)*a[i]-(s[i-1]-s[mid]);
        w[j][i]=L+R;
    }
}

:::

然后考虑其他的部分。因为此时是和 j 挂钩，而 k 也只和 k-1 挂钩，因此，此处我们考虑优化的话，只能对着 j 做。考虑去固定 k，然后考虑后续有什么性质。

:::success[知识点：四边形不等式]{open}

此处介绍一个东西叫做四边形不等式，具体的，我们取 p<q<r<s，然后对于一个二元函数 h(x,y)，若有 h(p,r)+h(q,s)\le h(p,s)+h(q,r)，那么我们就称其有 Monge 性质。我们记录 p(y)= \text{arg} \min_x h(x,y)，那么有 p(y) 关于 y 单调不减。

也就是说，我们可以从 y_1\le y_2 推出 p(y_1)\le p(y_2)。

:::

那么类似的，如果说我们固定 k，先不关注 dp_{j,k-1}，也就是说，我们去关注 w(j,i)，如果说满足上述的式子，那么就可以表明随着 i 的增加，最优的 j 一定是单调不减的。形式化的就是记录 P(i)=\text{arg} \min_j w(j,i)，然后在固定 k 的时候，P(i) 是随着 i 的增加而单调不减的。

那么现在的问题就是考虑如何证明。同样的，取 p<q<r<s，然后我们要证明的是 w(p,r)+w(q,s)\le w(p,s)+w(q,r)，稍微调换一下顺序，有 w(p,r)-w(q,r)\le w(p,s)-w(q,s)，我们不妨设 F(i)=w(p,i)-w(q,i)，那么原式就会变成证明 F(r) \le F(s)，也就是说要证明 F(i) 这个函数单调不降。

考虑如何证明。貌似可以画图然后分类讨论来做。思考一下 F(i) 这个函数的含义，很显然是我们放弃距离较近的一个村庄 q 而去选择一个较远的村庄 p 所需要付出的代价。如果可以证明在 p,q 固定的情况下，随着 i 的增加，这个差距会单调不减，那么就可以说明最原始的单调性。

考虑一个具体的村庄 t 对答案的贡献，他其实有两个大类，我们先考虑第一个：

不难发现对于这种情况，F(i) 肯定是随着 i 的增加而单调不减的。

还有一种情况就是 t\in (p,q) 的，很显然，第一次肯定是选择 q，那么贡献就是一个定值，记录为 o，考虑第二次，要选择的是 \min (a_i-a_t,a_t-a_p)，那么整体的贡献就是 \min(a_i-a_t,a_t-a_p)-o，很显然，是随着 i 的增大而单调不减的。

那么就可以说明 F(i) 是随着 i 的增加单调不减的，那么就可以说明在固定 k 的时候，P(i) 是随着 i 的单调不减的。

但是我们现在是只做完了和 w(l,r) 相关的，原本是还有个 dp_{j,k-1}。考虑观察。现在是有 w(p,r)-w(q,r)\le w(p,s)-w(q,s) 的，有个观察，我们令 L(j,i)=dp_{j,k-1}+w(j,i) 注意到 dp_{j,k-1} 只和 j 有关，那么我们完全可以在不等式的两侧同时加上 dp_{p,k-1}-dp_{q,k-1}，那么就有 L(p,r)-L(q,r)\le L(p,s)-L(q,s)。然后对应的单调性也就有了。

那么我们现在就是可以预见性的，在 k 一定的前提下，随着 i 的增加，j 一定是单调不减的，也就是把 i 给划分出了很多个区间，然后每个区间是一个 j 且是单调递增的。

那么就可以考虑一种分治的做法。具体的，我们知道一个区间 [l,r] 的对应的 j 是落在 [L,R] 的。那么我们可以求其中间值 mid，然后暴力求出来 mid 对应的 j_{mid}，那么有 [l,mid-1] 应该是落在 [L,j_{mid}] 的，[mid+1,r] 应该是落在 [j_{mid},R] 的，然后递归下去处理即可。

整体的大小就是 n\log n 级别的，最外层再枚举一个 k，整体的时间复杂度就是 \cal O(n^2 \log n) 的。代码如下：

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=3e3+10;
const ll INF=4e18;

int n,P,a[MAXN],s[MAXN],w[MAXN][MAXN];
ll f[MAXN],g[MAXN];
namespace yixing{
    inline void solve(int l,int r,int L,int R){
        if (l>r)return;
        int mid=(l+r)>>1,pos=-1;
        g[mid]=INF;
        for (int j=L;j<=min(mid-1,R);j++){
            ll val=f[j]+w[j][mid];
            if (val<g[mid])g[mid]=val,pos=j;
        }
        solve(l,mid-1,L,pos);
        solve(mid+1,r,pos,R);
    }
    inline void Main(){
        cin>>n>>P;
        for (int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+1+n);
        for (int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
        for (int j=1;j<=n;j++){
            int mid=j;
            for (int i=j+1;i<=n;i++){
                while (mid+1<i&&2*a[mid+1]<=a[j]+a[i])mid++;
                ll L=(s[mid]-s[j])-1ll*(mid-j)*a[j];
                ll R=1ll*(i-mid-1)*a[i]-(s[i-1]-s[mid]);
                w[j][i]=L+R;
            }
        }
        for (int i=1;i<=n;i++)f[i]=1ll*(i-1)*a[i]-s[i-1];
        for (int k=2;k<=P;k++){
            for (int i=1;i<=n;i++)g[i]=INF;
            solve(k,n,k-1,n-1);
            for (int i=1;i<=n;i++)f[i]=g[i];
        }
        ll ans=INF;
        for (int i=P;i<=n;i++){
            ll R=(s[n]-s[i])-1ll*(n-i)*a[i];
            ans=min(ans,f[i]+R);
        }
        cout<<ans<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}

:::

3. WQS 二分

考虑能否在这个基础上更进一步呢，考虑 P6246 [IOI 2000] 邮局 加强版 加强版。

:::success[知识点：WQS 二分]{open}

考虑说上述导致时间复杂度很高的原因是什么，不难发现说是这个恰好为 m 的限制过于奇葩了，而且限制很死，我们必须用 \cal O(n) 的时间去枚举然后求解。那么我们不难想到说，能不能用一种方法，让算法自己决定最终选择多少个呢？

貌似是可以的，我们考虑去增加一个权值 C。具体的，我们可以给每个邮局选择的时候增加一个权值 C，也就是说，我们建立一个邮局的时候，并不只是增加一个两个邮局之间的道路的贡献 w(l,r)，而是还要增加一个 C 的权值，由于我们是求的是最小值，因此，这里就有一个单调性，C 越大，我们最终选择的邮局就越少，因此，我们就可以去二分答案 C，找到一个最大的 C，满足在这个条件下，选择到的邮局数量不小于 m。

那么我们现在就可以把原本的 dp 转移式子给简化成 dp_i=\min_{j<i}\{dp_j +w(j+1,i)+C\}。

同时为了方便计算，我们此处将 w(l,r) 给定义为，区间 [l,r] 修一个邮局的最小代价，很显然应该修在中位数的地方。同时这样计算也是方便的，可以预处理然后通过前缀和在 \cal O(1) 里完成计算。

这样显然是正确的，因为我们会去枚举 j，也就是说一定会枚举到一个最优的一个划分方式，并不会出现最后选择的划分方式里有 [j+1,i] 中的一些村庄应该是到 [k,j] 的这个区间的邮局去的问题。

:::

有了这个关系我们现在就可以很轻易的做到 \mathcal O(n^2\log V)，只需要在最后做一次求解以保证答案是由当前的 C 贡献的，然后减去 C\times m 即可。考虑此处为什么是减去 m 而不是我们求得 cnt，注意到说这个函数是具有离散凸性的，因此，在临界 C 处，m 也是一定位于对应的支撑线段上的，所以说一定是合法的。

那么此时的问题就是，如何优化内层的 dp 了。还是考虑决策单调性的问题，就是随着 i 的增加，j 的变化是如何的。考虑四边形不等式。我们还是取 p<q<r<s，然后去证明 w(p,r)+w(q,s)\le w(p,s)+w(q,r)，也就是 w(p,s)-w(q,s)\le w(p,r)-w(q,r) 成立。我们不妨令 F(i)=w(p,i)-w(q,i)，那么就是要证明 F(i) 随着 i 的增加单调不减。

考虑利用函数单调性的定义，我们取 i,i+1，有 F(i+1)-F(i)=w(p,i+1)-w(q,i+1)-w(p,i)+w(q,i)，考虑对于这个做操作。

观察，我们要求的其实就是 w(l,i+1)-w(l,i) 这样的一个状物，我们考虑去求其变化值，具体的，对于 [l,i] 而言，中间值是 \lfloor \frac{i+l}{2} \rfloor，对于 [l,i+1] 而言。中间值是 \lfloor \frac{l+i+1}{2}\rfloor，不难发现，要么是向右挪一个，要么是没有变化，对于没有变化的，那么对于 [l,i] 肯定就是不会产生贡献的，那么唯一的贡献就是 a_{i+1}-a_{mid}。对于右移一格的，考虑会右移的原因，很显然就是 i+l 是一个奇数，也就是说，构成是一个奇数和一个偶数，也就是说，[i,l] 这段区间的长度是偶数，那么右移一格就是镜像的，那么自然不会有变化，唯一的增加仍然是 a_{i+1}-a_{mid}。所以说 w(l,i+1)-w(l,i)=a_{i+1}-a_{mid}。

那么 F(i+1)-F(i)=a_{\lfloor \frac{i+q+1}{2}\rfloor}-a_{\lfloor\frac{i+p+1}{2}\rfloor}，由于 p<q，所以 \lfloor \frac{i+q+1}{2}\rfloor \ge \lfloor\frac{i+p+1}{2}\rfloor，所以 a_{\lfloor \frac{i+q+1}{2}\rfloor} \ge a_{\lfloor\frac{i+p+1}{2}\rfloor}，因此 F(i+1)-F(i)\ge 0，因此，F(i) 单调递增。

然后又因为 dp_j 只和 j 有关，C 也是一个常数，dp 方程的转移方程那也就是单调递增的了。

也就是说，内层的转移可以用决策单调性进行优化。考虑用队列来完成这个事情，具体的，我们开三个变量 k,l,r 表示对于一个选择 k，他是在 [l,r] 是处于最优的状态，同时我们也以这个为第一关键字。那么我们从前往后枚举 i，令 h 等于当前队列的队首，我们可以考虑把那些满足 h.r<i 的队首全部剔除了，那么此时留下的队首就是答案，直接转移即可。

然后就是考虑剔除一些劣质的答案，具体的，对于一个现在在队末的方案 t，如果说在 i+1 或者 t.l 的位置，i 比 t.k 更优，那么就代表这个 t 就是完全无用的，从头到尾都不可能被使用，可以直接不要了，弹出即可。

然后就考虑入队列，由于此时的队末的元素是有用的，那么我们要找的就是 i 会在何时超过 t.k，考虑用之前的方案，去二分即可。此处需要考虑一个细节，就是平局的问题，由于我们此处求的是满足 cnt\ge m 的最大的 C，所以说对于两个决策，在 p 处代价相同的时候，我们应该回去选择 cnt 更大的一个。当然你可以选择较小的一个，然后把二分的条件改成求满足 cnt\le m 的最大的 C。

这样的时间复杂度就是 \mathcal O(n \log n\log V) 的，就可以过了。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=5e5+10;
const int INF=1e9+10;

int n,m,a[MAXN];
ll s[MAXN];
struct Node{ll val,cnt;}f[MAXN];
namespace yixing{
    struct Q{int k,l,r;}q[MAXN];
    inline ll w(int l,int r){
        ll mid=(l+r)>>1;
        return 1ll*a[mid]*(mid-l+1)-(s[mid]-s[l-1])+(s[r]-s[mid])-(r-mid)*a[mid];
    }
    inline bool better(int x,int y,int k){
        ll X=f[x].val+w(x+1,k),Y=f[        y].val+w(y+1,k);
        if (X!=Y)return X<Y;
        return f[x].cnt>f[y].cnt;
    }
    inline int check(int C){
        int head=1,tail=1;
        q[1]={0,1,n};
        for (int i=1;i<=n;i++){
            while (head<=tail&&q[head].r<i)head++;
            int j=q[head].k;
            f[i].val=f[j].val+w(j+1,i)+C;
            f[i].cnt=f[j].cnt+1;
            while (head<=tail){
                int L=max(q[tail].l,i+1);
                if (better(i,q[tail].k,L))tail--;
                else break;
            }
            if (tail<head){q[++tail]={i,i+1,n};continue;}
            int old=q[tail].k;
            int l=max(q[tail].l,i+1),r=n,pos=n+1;
            while (l<=r){
                int mid=(l+r)>>1;
                if (better(i,old,mid))pos=mid,r=mid-1;
                else l=mid+1;
            }
            if (pos<=n){
                q[tail].r=pos-1;
                q[++tail]={i,pos,n};
            }
        }
        return f[n].cnt;
    }
    inline void Main(){
        cin>>n>>m;
        for (int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+1+n);
        for (int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
        int l=0,r=INF,res=0;
        while (l<=r){
            int mid=(l+r)>>1;
            if (check(mid)>=m)res=mid,l=mid+1;
            else r=mid-1;
        }
        check(res);
        cout<<f[n].val-res*m<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
  }

:::

4. 一些例题

考虑 P1912 [NOI2009] 诗人小 G 这道题。

分析题目，可知这道题是简单的。具体的我们令 dp_{i,k} 表示当前到第 i 个短句，然后前面是分成了 k 段，那么很显然就有：

dp_{i,k}=\min_{j<i} \{dp_{j,k-1}+ w(j+1,i)\}

考虑 w(l,r) 如何计算。具体的我们考虑做一个前缀和 s_i，那么 w(l,r)=[s_r-s_{l-1}+(r-l)-L]^P，其中 r-l 是对应的空格。

考虑优化，注意到 k 是无意义的，可以直接丢掉。那么现在就是：

dp_i=\min_{j<i}\{dp_j+w(j+1,i)\}

继续考虑优化，考虑决策单调性。

把四边形不等式搬出来，有取 p<q<r<s，求证 w(p,r)+w(q,s)\le w(p,s)+w(q,r)，同样的，考虑移项。有：

w(p,r)-w(q,r)\le w(p,s)-w(q,s)

令 F(i)=w(p,i)-w(q,i)，那么要证明的就是 F(i) 随着 i 的增大而增大。

考虑这个事情，单独看 w(p,i) 而言，在固定 p 的情况下，w(p,i) 肯定是随着 i 的增大而增大的，而且趋势不小。然后考虑 F 了，发现直接分析或者分讨貌似是困难的，我们考虑用定义来尝试一下。具体的，我们就是要去考虑 F(i+1)-F(i)=w(p,i+1)-w(q,i+1)-w(p,i)+w(q,i)，简单规整一下，就有 w(p,i+1)-w(p,i)-(w(q,i+1)-w(q,i))，那么就是对于这个玩意去思考，也就是说我们要思考的就是 w(l,i+1)-w(l,i)。

我们把这个式子写出来，有 [s_{i+1}-s_{l-1}+(i+1-l)]^P-[s_i-s_{l-1}+(i-l)]^P，由于此处的 -L 只是对函数有左右移动的问题，所以说不用管。

我们令 A_i=s_i-s_{l-1}+(i-l)，那么有 A_{i+1}^P-A_i^P，对于这个而言注意到 A_{i+1}-A_i 是一个定值 s_{i+1}-s_i+1，我们设这个差值为 k，那么原式就应该是 B^P-(B-k)^P 这样的一个形式。

考虑固定 i+1,i，然后记 Q(i)=i^P-(i-k)^P，那么 w(l,i+1)-w(l,i) 就是 Q(s_l)，也就是说 F(i+1)-F(i) 可以转换成 Q(s_p)-Q(s_q) 的形式。由于 p<q 且 s_i 是单调递增的，那么 s_p<s_q 是显然的，那么现在就是要思考 Q(i) 的单调性了。画图或者对其求导，可知在 P>1 的情况下，Q(i) 是单调递增的，在 P=1 的情况下，是常数。那么就可以证明到 F(i+1)-F(i)\ge 0，那么也就可以证明 F(i) 是单调递增的了，也就可以说明最原本的式子是有单调性的了。

注意到题目还要求输出整体的排版方式，考虑记录前驱，那么这里就不太方便用分治来做了，考虑单调队列的方式即可。

一个细节，string 做加法是 \cal O(n) 的，因此在合并的时候，直接存储左右边界而不是存储字符串即可。

另外一个细节，此处不能在 >10^{18} 的时候就直接赋值成 10^{18}+1，之类的，因为这种会导致原本的决策单调性不成立，所以说考虑用 __int128 或是 long double 来存储即可。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int MAXN=1e5+10;
const ld INF=1e18;
int n,L,p;
string s[MAXN];
ld dp[MAXN],pre[MAXN],sum[MAXN],len[MAXN];
namespace Tool{
    inline ld quick_pow(ld a,ll b){
        ld res=1;
        while (b){
            if (b&1)res=res*a;
            a=a*a;
            b>>=1;
        }
        return res;
    }
}
namespace yixing{
    struct Node{int k,l,r;}q[MAXN];
    inline ld w(int l,int r){return Tool::quick_pow(llabs(sum[r]-sum[l-1]+(r-l)-L),p);}
    inline bool better(int x,int y,int k){
        ld X=dp[x]+w(x+1,k),Y=dp[y]+w(y+1,k);
        return X<=Y;
    }
    struct sta{int l,r;};
    inline void print(){
        stack<sta> st;
        int pos=n;
        while (pos){
            st.push(sta{pre[pos]+1,pos});
            pos=pre[pos];
        }
        while (!st.empty()){
            int l=st.top().l,r=st.top().r;
            for (int i=l;i<=r;i++){
                cout<<s[i];
                if (i!=r)cout<<" ";
            }
            cout<<"\n";
            st.pop();
        }
    }
    inline void solve(){
        int head=1,tail=0;
        q[++tail]={0,1,n};
        memset(dp,0,sizeof(dp)),memset(pre,0,sizeof(pre));
        for (int i=1;i<=n;i++){
            while (q[head].r<i)head++;
            int j=q[head].k;
            dp[i]=dp[j]+w(j+1,i),pre[i]=j;
            while (head<=tail){
                int L=max(q[tail].l,i+1);
                if (better(i,q[tail].k,L))tail--;
                else break;
            }
            if (head>tail){head=tail=1,q[1]={i,i+1,n};continue;}
            int old=q[tail].k;
            int l=max(q[tail].l+1,i+1),r=n,pos=n+1;
            while (l<=r){
                int mid=(l+r)>>1;
                if (better(i,old,mid))pos=mid,r=mid-1;
                else l=mid+1;
            }
            if (pos<=n){
                q[tail].r=pos-1;
                q[++tail]={i,pos,n};
            }
        }
        if (dp[n]>INF)cout<<"Too hard to arrange\n";
        else {
            cout<<(ll)dp[n]<<"\n";
            print();    
        }
    }
    inline void Main(){
        cin>>n>>L>>p;
        for (int i=1;i<=n;i++){
            cin>>s[i];
            len[i]=s[i].length(),sum[i]=sum[i-1]+len[i];
        }
        solve();
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--){
        yixing::Main();
        cout<<"--------------------";
        if (T!=0)cout<<"\n";
    }
    return 0;
}

:::

考虑 P3724 [AHOI2017/HNOI2017] 大佬 这道题。

分析一下题目，不难发现，操作 2 和其他操作是独立的，只有操作 2 和大佬的攻击会对自身的血量有影响，而我们要保证自己是不能死的，所以说我们貌似可以基于这两个操作，dp 求出来我们最多可以用多少天来做操作 1,3,4,5。具体的，我们设 dp_{i,j} 表示当前在第 i 天，然后自己的血量是 j，那么考虑分类讨论一下，若当前什么都不做，那么答案应该是 dp_{i,j-a_i}=\max_{j}dp_{i-1,j}+1，如果进行回血，那么答案就是 dp_{i,\min\{\text{mc},j-a_i+w_i\}}=\max_j dp_{i-1,j}。很显然二者是 \cal O(n^2) 的，肯定没有问题。

考虑我们此处的答案，貌似应该是全局的最大值，因为我们可能中间就把大佬给打死了，不一定要到 n。

:::info[Code]{open}

inline void init_dp(){
    memset(dp,0xc0,sizeof(dp));
    dp[0][mc]=0;D=0;
    for (int i=1;i<=n;i++){
        for (int j=a[i];j<=mc;j++){
            if (dp[i-1][j]<0)continue;
            int x=j-a[i];
            dp[i][x]=max(dp[i][x],dp[i-1][j]+1);
            x=min(mc,j-a[i]+w[i]);
            dp[i][x]=max(dp[i][x],dp[i-1][j]);
        }
        for (int j=0;j<=mc;j++)D=max(D,dp[i][j]);
    }
}

:::

那么我们现在就变成了，通过操作 1,3,4,5，把大佬刚好打到 0。思考一下如何入手。注意到说操作 5 最多只能操作 2 次，因此我们考虑对其讨论。

我们记录上述的最大值为 D，如果说一次操作 5 都不使用的话，那么需要满足的条件应该是 C\le D，也就是通过操作 1 把大佬给磨死。

如果说只操作一次的话，我们要找的就是看是否有一个三元组 (F,L,d)，满足 d\le D 且 C \ge F，且 D-d\ge C-F。如果存在，那么就说明是可行的。

如果说操作两次的话，我们要找的就是两个三元组 (F_1,L_1,d_1) 和 (F_2,L_2,d_2) 满足 F_1+F_2 \le C 且 d_1+d_2 \le D，且 C-F_1-F_2 \le D-d_1-d_2。

把后面的式子移一下项，有 C-D \le F_1-d_1+F_2-d_2。不难想到，如果说我们可以求出所有的三元组，然后按照 F 为第一关键字，d 为第二关键字进行排序。我们就貌似可以用一个类似于双指针的玩意完成这个东西。具体的，我们记录现在有用的三元组的数量是 cnt，然后按照上述方式已经排完序了，同时我们考虑把 F 相同，d 不相同的三元组中，d 最小的进行保留，然后其他的全丢了。

然后我们考虑从末尾进行枚举 i，同时维护一个 p 从头开始，由于 i 偏大，那么考虑移动 p 的条件就是满足 F_i+F_p\le C，而因为此时的 i 已经固定，也就是说 F_i-d_i 是定值，那么贪心的想，不难想到我们应该要求的是 F_p-d_p 的最大值，也就是说维护一个 \max 即可。这样就可以在 \cal O(n) 的时间复杂度内求出答案。

那么现在的问题就是如何求三元组。考虑暴力的方式。具体的，考虑 BFS。即 (x,y) 对应 (F,L)，然后深度 dep 对应 d，然后用 hash 来存储。考虑有哪些路径，不难发现只有两种，一种是 (F,L) \xrightarrow {3}(F,L+1)，一种是 (F,L)\xrightarrow{4}(F\times L,L)，然后对于二者而言深度的增加都是 +1，分析限制，由于你最终还需要一天来完成操作 5，所以说，对于 L 而言，必须满足 L\le D-1，同理 F\times L 应 \le C_{\text{max}}。同时还需要判重，因为我们是 BFS 的，所以说先到的 (F,L) 肯定比后到的 (F,L) 的 d 要小，因此我们在 hash 的时候可以判一下重。

由于在 L=1 的时候，去做乘法一定是无用的，因此，我们至少都会在 L\ge 2 的时候做乘法，而 C_{\text{max}}\le 10^8，所以说，F 的变化只有 26 次左右，很小。然后 L 和深度 d 又是 \cal O(n) 级别的，所以说整体的级别大概就是 10^5 这个级别，很小，所以说暴力是完全没有问题的。

BFS 完之后，处理一下去重的问题即可。

:::info[Code]

include<bits/stdc++.h>

define ll long long

define uch unsigned char

using namespace std; const int MAXN=105; const int MAXS=7e6+10; const int Mod=2e6+3; const int INF=1e9; int n,m,mc,a[MAXN],w[MAXN],c[MAXN],cnt; ll dp[MAXN][MAXN],D,maxC; namespace HASH{ struct Node{ int F,nxt; uch L,d; }s[MAXS]; int head[Mod],tot; inline int Hash(int F,int L){return (1ullF233+L)%Mod;} inline bool insert(int F,int L,int dep){ int h=Hash(F,L); for (int i=head[h];i;i=s[i].nxt)if (s[i].F==F&&s[i].L==L)return 0; s[++tot]={F,head[h],(uch)L,(uch)dep}; head[h]=tot; return 1; } inline bool cmp(const Node a1,const Node a2){ if (a1.F!=a2.F)return a1.F<a2.F; return a1.d<a2.d; } } namespace yixing{ inline void init_dp(){ memset(dp,0xc0,sizeof(dp)); dp[0][mc]=0;D=0; for (int i=1;i<=n;i++){ for (int j=a[i];j<=mc;j++){ if (dp[i-1][j]<0)continue; int x=j-a[i]; dp[i][x]=max(dp[i][x],dp[i-1][j]+1); x=min(mc,j-a[i]+w[i]); dp[i][x]=max(dp[i][x],dp[i-1][j]); } for (int j=0;j<=mc;j++)D=max(D,dp[i][j]); } } inline void bfs(){ if (D<4||maxC<=D)return; using namespace HASH; insert(1,1,1); for (int u=1;u<=tot;u++){ int F=s[u].F,L=s[u].L,dep=s[u].d; if (dep>=D-1)continue; if (1llFL>maxC)continue; if (1llF(L+1)<=maxC)insert(F,L+1,dep+1); if (L>1&&1llFL<=maxC)insert(FL,L,dep+1); } sort(s+1,s+tot+1,cmp); cnt=0; for (int i=1,j;i<=tot;i=j){ j=i+1; while (j<=tot&&s[j].F==s[i].F)j++; if (s[i].F>1)s[++cnt].F=s[i].F,s[cnt].d=s[i].d+1; } } inline bool check(int c){ using namespace HASH; if (c<=D)return 1; for (int i=1;i<=cnt;i++){ int F=s[i].F,d=s[i].d; if (F>c)break; if (c-F<=D-d)return 1; } int p=1,mx=-INF; for (int i=cnt;i>=1;i--){ int F=s[i].F,d=s[i].d; while (p<=cnt&&1lls[p].F+F<=c){ mx=max(mx,s[p].F-(int)s[p].d); p++; } if (mx!=-INF&&mx+F-d>=c-D)return 1; } return 0; } inline void Main(){ cin>>n>>m>>mc; for (int i=1;i<=n;i++)cin>>a[i]; for (int i=1;i<=n;i++)cin>>w[i]; for (int i=1;i<=m;i++)cin>>c[i],maxC=max(maxC,1ll*c[i]); init_dp(); bfs(); for (int i=1;i<=m;i++)cout<<check(c[i])<<"\n"; } } int main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); yixing::Main(); return 0; }

#include<bits/stdc++.h>
#define ll long long
#define uch unsigned char
using namespace std;
const int MAXN=105;
const int MAXS=7e6+10;
const int Mod=2e6+3;
const int INF=1e9;
int n,m,mc,a[MAXN],w[MAXN],c[MAXN],cnt;
ll dp[MAXN][MAXN],D,maxC;
namespace HASH{
    struct Node{
        int F,nxt;
        uch L,d;
    }s[MAXS];
    int head[Mod],tot;
    inline int Hash(int F,int L){return (1ull*F*233+L)%Mod;}
    inline bool insert(int F,int L,int dep){
        int h=Hash(F,L);
        for (int i=head[h];i;i=s[i].nxt)if (s[i].F==F&&s[i].L==L)return 0;
        s[++tot]={F,head[h],(uch)L,(uch)dep};
        head[h]=tot;
        return 1;
    }
    inline bool cmp(const Node a1,const Node a2){
        if (a1.F!=a2.F)return a1.F<a2.F;
        return a1.d<a2.d;
    }
}
namespace yixing{
    inline void init_dp(){
        memset(dp,0xc0,sizeof(dp));
        dp[0][mc]=0;D=0;
        for (int i=1;i<=n;i++){
            for (int j=a[i];j<=mc;j++){
                if (dp[i-1][j]<0)continue;
                int x=j-a[i];
                dp[i][x]=max(dp[i][x],dp[i-1][j]+1);
                x=min(mc,j-a[i]+w[i]);
                dp[i][x]=max(dp[i][x],dp[i-1][j]);
            }
            for (int j=0;j<=mc;j++)D=max(D,dp[i][j]);
        }
    }
    inline void bfs(){
        if (D<4||maxC<=D)return;
        using namespace HASH;
        insert(1,1,1);
        for (int u=1;u<=tot;u++){
            int F=s[u].F,L=s[u].L,dep=s[u].d;
            if (dep>=D-1)continue;
            if (1ll*F*L>maxC)continue;
            if (1ll*F*(L+1)<=maxC)insert(F,L+1,dep+1);
            if (L>1&&1ll*F*L<=maxC)insert(F*L,L,dep+1);
        }
        sort(s+1,s+tot+1,cmp);
        cnt=0;
        for (int i=1,j;i<=tot;i=j){
            j=i+1;
            while (j<=tot&&s[j].F==s[i].F)j++;
            if (s[i].F>1)s[++cnt].F=s[i].F,s[cnt].d=s[i].d+1;
        }
    }
    inline bool check(int c){
        using namespace HASH;
        if (c<=D)return 1;
        for (int i=1;i<=cnt;i++){
            int F=s[i].F,d=s[i].d;
            if (F>c)break;
            if (c-F<=D-d)return 1;
        }
        int p=1,mx=-INF;
        for (int i=cnt;i>=1;i--){
            int F=s[i].F,d=s[i].d;
            while (p<=cnt&&1ll*s[p].F+F<=c){
                mx=max(mx,s[p].F-(int)s[p].d);
                p++;
            }
            if (mx!=-INF&&mx+F-d>=c-D)return 1;
        }
        return 0;
    }
    inline void Main(){
        cin>>n>>m>>mc;
        for (int i=1;i<=n;i++)cin>>a[i];
        for (int i=1;i<=n;i++)cin>>w[i];
        for (int i=1;i<=m;i++)cin>>c[i],maxC=max(maxC,1ll*c[i]);
        init_dp();
        bfs();
        for (int i=1;i<=m;i++)cout<<check(c[i])<<"\n";
    }
}
int main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}

:::

考虑 P5574 [CmdOI2019] 任务分配问题 这道题。

很容易转换成 dp_{i,k}=\min_{j<i} \{dp_{j,k-1}+w(j+1,i) \}，那么问题就是在于 w(j+1,i) 怎么求以及如何优化。

比较显然的一个事情是，w(j+1,i) 是一个类似于逆序对的状物，所以说他的单调性是显然的，因此可以用决策单调性来处理，那么现在的问题就是如何处理这个 w。

首先一个想法就是用树状数组来存储，因为你考虑在分治的过程中，你是要一个一个进行枚举的，所以说这个过程就是可以直接用树状数组来做。

但是就是问题在于，这样的时间复杂度是 \cal O(n^2 \log n) 的绝对过不了，外面还有一层 k。

考虑一种比较经典的策略，即对于一个区间，从 [l,r] 到 [l-1,r] 的变化是什么，或者说，这样的逆序对的变化是多少。这个是简单的，我们令 l-1 处的值是 a_{l-1}，那么答案变化的量就是当前树状数组中比 a_{l-1} 大的元素的个数。从 [l,r] 变化到 [l+1,r] 或者 [l,r-1] 或者 [l,r+1] 是类似的。

注意到这种本质上来说就是莫队，而又因为，我们是在分治的时候进行的处理，所以说相邻区间之间的差距很小，同时二者的时间复杂度也不再是嵌套的，这样就可以过了。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2.5e4+10;
const int INF=1e9+10;

int n,k,a[MAXN];
ll f[MAXN],g[MAXN];

struct BIT{
    int tree[MAXN],cnt=0;
    inline void update(int p,int x){
        cnt+=x;
        for (int i=p;i<=n;i+=(i&(-i)))tree[i]+=x;
    }
    inline int query(int p){
        int res=0;
        for (int i=p;i;i-=(i&(-i)))res+=tree[i];
        return res;
    }
}T;
namespace yixing{
    int ql=1,qr=0;ll w=0;
    inline void addL(){
        w+=T.cnt-T.query(a[--ql]);
        T.update(a[ql],1);
    }
    inline void addR(){
        w+=T.query(a[++qr]-1);
        T.update(a[qr],1);
    }
    inline void delL(){
        w-=T.cnt-T.query(a[ql]);
        T.update(a[ql++],-1);
    }
    inline void delR(){
        w-=T.query(a[qr]-1);
        T.update(a[qr--],-1);
    }
    inline void move(int l,int r){
        while (ql>l)addL();
        while (qr<r)addR();
        while (ql<l)delL();
        while (qr>r)delR();
    }
    inline void solve(int l,int r,int L,int R){
        if (l>r)return;
        int mid=(l+r)>>1,pos=-1;
        g[mid]=INF;
        for (int j=min(R,mid-1);j>=L;j--){
            move(j+1,mid);
            if (g[mid]>f[j]+w)g[mid]=f[j]+w,pos=j;
        }
        solve(l,mid-1,L,pos),solve(mid+1,r,pos,R);
    }
    inline void Main(){
        cin>>n>>k;
        for (int i=1;i<=n;i++)cin>>a[i];
        memset(f,0x3f,sizeof(f));
        f[0]=0;
        for (int i=1;i<=k;i++){
            memset(g,0,sizeof(g));
            solve(i,n,i-1,n-1);
            for (int i=0;i<=n;i++)f[i]=g[i];
        }
        cout<<f[n]<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    yixing::Main();
    return 0;
}

:::