决策单调性之四边形不等式优化（决策单调性优化 dp）¶

通常是用来证明dp的一些特殊性质，会和其它dp优化方法结合，如斜率优化。

四边形不等式优化和斜率优化本质上都是利用了**单调性**，所以有一些时候可以通用。

关于决策单调性优化 dp，下面的博客讲的很清楚

www.luogu.com.cn

下面是一些摘录

什么是决策单调性优化 dp？

形如 $dp_i=\min/\max(dp_j+f(j,i))$ 这类的式子，令 $t_i$ 为使得 $dp_i$ 取到 $\min/\max$ 的 $j$，（其实 $t_i$ 就叫最优决策）若 $t_i$ 具有单调性，则这个 dp 式子就满足决策单调性。

具体如何判断？

令 $f_j(i)$ 为用 $j$ 转移时 $dp_i$ 的值（即 $dp_j+f(j,i)$）。

若对于任意 $j_1<j_2$，$f_{j_1}(i)$ 和 $f_{j_2}(i)$ 的函数图像至多有一个交点，在这个交点之前是 $f_{j_1}(i)$ 更小，在这个交点后是 $f_{j_2}(i)$ 更小，那么这个问题就满足决策单调性。

因为交点之前的 $i$ 的决策都是 $j_1$，交点后的决策都是 $j_2$。正好满足决策单调性。

（其实如果反之，在交点前都是 $j_2$ 更优而交点后都是 $j_1$ 更优，是一种不同的决策单调性问题，因与本题无关此处略去。）

决策单调性的优化方法大致有决策栈，决策队列和分治。下面说明决策队列优化。

决策队列具体是这样做的：

队列维护决策三元组 $(p,l,r)$ 表示目前看来 $t_l,t_{l+1}\dots t_r$ 都是 $p$。一般来说一开始队列里只有三元组 $(0,1,n)$。

每次计算 $dp_i$ 时，就先把队列中无用的三元组弹出（$r<i$），并把新的队首的 $l$ 设为 $i$。此时 $i$ 在队首，所以 $i$ 的决策就是队首的 $p$。用 $dp_p$ 更新 $dp_i$。

接下来从队尾开始扫，如果用 $i$ 来更新队尾的 $l$ 比队尾的 $p$ 更新队尾的 $l$ 更优，说明队尾的决策应该比 $p$ 更大（因为我们从小到大枚举 $i$），那么根据决策单调性，整个三元组中的决策都比 $p$ 大。于是便可以弹出队尾。

到最后用 $i$ 来更新队尾的 $l$ 没有队尾的 $p$ 更新队尾的 $l$ 优。那么我们就要找出决策变为 $i$ 的分界点。由于决策具有单调性，我们可以二分。二分边界就是队尾三元组的 $l$ 和 $n$（为什么不是 $r$？因为可能这整个三元组都满足原来的决策，此时二分却会把最后一个元素拆走）。

二分出分界点 $x$ 后，队尾三元组的 $r$ 应改为 $x-1$（之后的决策都要变）。队尾再新加入一个三元组 $(i,x,n)$，表示 $x$ 到 $n$ 的决策都可以改为更优的 $i$。

至此算法结束。

因为每一个 $i$ 都会至多添加一个三元组，对一个三元组进行二分，又因为一个三元组至多被删除一次，所以复杂度为 $O(n\log n)$。

[NOI2009] 诗人小G¶

题目描述

小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。

小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

输入格式

输入文件中的第一行为一个整数 $T$，表示诗的数量。

接下来为 $T$ 首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数 $N,L,P$，其中：$N$ 表示这首诗句子的数目，$L$ 表示这首诗的行标准长度，$P$ 的含义见问题描述。

从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成（ASCII 码 $33 \sim 127$，但不包含 -）。

输出格式

于每组测试数据，若最小的不协调度不超过 $10^{18}$，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。

如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过 $10^{18}$，则输出 Too hard to arrange。每组测试数据结束后输出 --------------------，共 20 个 -，- 的 ASCII 码为 45，请勿输出多余的空行或者空格。

前两组输入数据中每行的实际长度均为 $6$，后两组输入数据每行的实际长度均为 $4$。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中（可参见样例中第二组数据）。每行末尾没有空格。

思路¶

很显然的 dp 方程：

$f_i=\min(f_j+|\text{sum}_i-\text{sum}_j+i-j-1-L|^P)$

其中$\text{sum}_x=\sum_{i=1}^xa_i$，即这里使用前缀和优化。a_i为第i个句子的长度。那么怎么优化呢？因为有一个P次方，数据结构优化是没办法了。

我们可以发现$|\text{sum}_i-\text{sum}_j+i-j-1-L|^P$是存在决策单调性的。下面考虑证明：

对于(i,j)(k,m)，设i<j,k<m，且ii，则满足决策单调性。

证明如下

www.luogu.com.cn

以下是节选

我们只需证明函数$G_j(i)=|\text{sum}_i+i-(\text{sum}_j+j)-(1+L)|^P$满足四边形不等式。

$\Leftrightarrow\ G_j(i+1)+G_{j+1}(i)\geq G_{j}(i)+G_{j+1}(i+1)$

#include <bits/stdc++.h>
#define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
using namespace std;
#define int long long
#define pii pair<int, int>

#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define ld long double

#define rd read()
int read() {
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-')
      ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
void write(int out) {
  if (out < 0)
    putchar('-'), out = -out;
  if (out > 9)
    write(out / 10);
  putchar(out % 10 + '0');
}

const int N = 2e5 + 15;
const int INF = 1e9 + 5;
const int MOD = 998244353;

int n,L,P,s[N],q[N],k[N],pr[N];
ld f[N];
char str[N][33];

ld ksm(ld b){
    ld a=1;
    for(int k=P;k;k>>=1,b*=b)
        if(k&1)a*=b;
    return a;
}
ld Calc(int i,int j){return f[j]+ksm(abs(s[i]-s[j]-L));}
int bound(int x,int y){
    int l=x,r=n+1,m;
    while(l<r){
        m=(l+r)>>1;
        Calc(m,x)>=Calc(m,y)?r=m:l=m+1;
    }
    return l;
}
signed main(){
    int T=rd,i,h,t;
    while(T--){
        n=rd;L=rd+1;P=rd;
        for(i=1;i<=n;++i){
            if(scanf("%s",str[i]));
            s[i]=s[i-1]+strlen(str[i])+1;
        }
        for(q[i=h=t=1]=0;i<=n;++i){
            while(h<t&&k[h]<=i)++h;
            f[i]=Calc(i,q[h]);pr[i]=q[h];
            while(h<t&&k[t-1]>=bound(q[t],i))--t;
            k[t]=bound(q[t],i);q[++t]=i;
        }
        if(f[n]>1e18)puts("Too hard to arrange");
        else{
            printf("%.0Lf\n",f[n]);
            for(q[t=0]=i=n;i;q[++t]=i=pr[i]);
            for(;t;--t){
                for(i=q[t]+1;i<q[t-1];++i)
                    printf("%s ",str[i]);
                puts(str[i]);
            }
        }
        puts("--------------------");
    }
    return 0;
}

数据规模与约定

测试点	$T$	$N$	$L$	$P$
$1$	$\le 10$	$\le18$	$\le 100$	$\le5$
$2$	$\le 10$	$\le 2\times 10^3$	$\le 6\times 10^4$	$\le10$
$3$	$\le 10$	$\le 2\times 10^3$	$\le 6\times 10^4$	$\le10$
$4$	$\le 5$	$\le 10^5$	$\le 200$	$\le10$
$5$	$\le 5$	$\le 10^5$	$\le 200$	$\le10$
$6$	$\le 5$	$\le 10^5$	$\le 3\times 10^6$	$2$
$7$	$\le 5$	$\le 10^5$	$\le 3\times 10^6$	$2$
$8$	$\le 5$	$\le 10^5$	$\le 3\times 10^6$	$\le10$
$9$	$\le 5$	$\le 10^5$	$\le 3\times 10^6$	$\le10$
$10$	$\le 5$	$\le 10^5$	$\le 3\times 10^6$	$\le10$

所有句子的长度不超过 $30$ 。

[HNOI2008] 玩具装箱¶

题目描述

P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

为了方便整理，P教授要求：

在一个一维容器中的玩具编号是连续的。
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望所有容器的总费用最小。

输入格式

第一行有两个整数，用一个空格隔开，分别代表 $n$ 和 $L$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 件玩具的长度 $C_i$。

输出格式

输出一行一个整数，代表所有容器的总费用最小是多少。

对于全部的测试点，$1 \leq n \leq 5 \times 10^4$，$1 \leq L \leq 10^7$，$1 \leq C_i \leq 10^7$。

std

#include <bits/stdc++.h>
#define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
using namespace std;
#define int long long
#define pii pair<int, int>

#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)

#define X(j) S[j]
#define Y(j) (dp[j]+(S[j]+L)*(S[j]+L))

#define rd read()
int read() {
  int xx = 0, ff = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-')
      ff = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    xx = xx * 10 + (ch - '0'), ch = getchar();
  return xx * ff;
}
void write(int out) {
  if (out < 0)
    putchar('-'), out = -out;
  if (out > 9)
    write(out / 10);
  putchar(out % 10 + '0');
}

const int N = 2e5 + 15;
const int INF = 1e9 + 5;
const int MOD = 1 << 30;

int i,j,n,L,h=1,t=0,Q[N],S[N],dp[N];

inline int min(int a,int b){return a<b?a:b;}
inline long double slope(int i,int j){return (long double)(Y(j)-Y(i))/(X(j)-X(i));}
signed main(){
    scanf("%lld%lld",&n,&L);++L; 
    for(i=1;i<=n;S[i]+=S[i-1]+1,++i)scanf("%lld",&S[i]);
    Q[++t]=0;
    for(i=1;i<=n;++i){
        while(h<t&&slope(Q[h],Q[h+1])<=2*S[i])++h;
        dp[i]=dp[j=Q[h]]+(S[i]-S[j]-L)*(S[i]-S[j]-L);
        while(h<t&&slope(Q[t-1],Q[t])>=slope(Q[t-1],i))--t;
        Q[++t]=i;
    }
    printf("%lld",dp[n]);
}

[IOI2000] 邮局¶

题目描述

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

输入格式

第一行包含两个整数：第一个是村庄 $V$ 的数量，第二个是邮局的数量 $P$。

第二行包含 $V$ 个整数。这些整数是村庄的位置。

输出格式

第一行包含一个整数$S$，它是每个村庄与其最近的邮局之间的所有距离的总和。

对于 $40\%$ 的数据，$V \leq 300$。

对于 $100\%$ 的数据，$1 \leq P \leq 300$，$P \leq V \leq 3000$，$1 \leq $ 村庄位置 $\leq 10000$。

思路¶

提前预处理出w，w是可以O(V2)递推出来的，根据放置一个邮局，邮局位置总是在中位数处，便可推得。

然后因为dp满足四边形不等式，所以对于dp[i][j]的最优决策d[i][j]，d[i][j−1]≤d[i][j]≤d[i+1][j]

于是状态转移dp[i][j]时，从[d[i][j−1],d[i+1][j]]中找最优决策。

/*
CB Ntsc111
*/

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define ps second

#define err cerr<<"Error"
#define rd read()
// #define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
inline void write(int out)
{
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}

const int INF = 1e9;
const int N = 3e3+5;
const int M = 1e6+5;
const int S=1e6+5;
const int maxlog = 10;

int v,p,pos[N],dp[N][N],w[N][N],d[N][N];

void init() {
    for(int l=1;l<=v;l++) {
        w[l][l]=0;
        for(int r=l+1;r<=v;r++) {
            w[l][r]=w[l][r-1]+pos[r]-pos[l+r>>1];
        }
    }
}

int main() {
  v=rd,p=rd;
    for(int i=1;i<=v;i++) pos[i]=rd;

    init();
    sort(pos+1,pos+v+1);
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int j=1;j<=p;j++) {
        d[v+1][j]=v;
        for(int i=v;i>=1;i--) {
            int minn=INF,minid;
            for(int k=d[i][j-1];k<=d[i+1][j];k++) {
                if(dp[k][j-1]+w[k+1][i]<minn) {
                    minn=dp[k][j-1]+w[k+1][i];
                    minid=k;
                }
            }
            dp[i][j]=minn;
            d[i][j]=minid;
        }
    }

    cout<<dp[v][p]<<endl;

    return 0;
}

/*
4
()()
1 -1 5 11

4
()()
1 6 5 11
*/

测试点	\(T\)	\(N\)	\(L\)	\(P\)
\(1\)	\(\le 10\)	\(\le18\)	\(\le 100\)	\(\le5\)
\(2\)	\(\le 10\)	\(\le 2\times 10^3\)	\(\le 6\times 10^4\)	\(\le10\)
\(3\)	\(\le 10\)	\(\le 2\times 10^3\)	\(\le 6\times 10^4\)	\(\le10\)
\(4\)	\(\le 5\)	\(\le 10^5\)	\(\le 200\)	\(\le10\)
\(5\)	\(\le 5\)	\(\le 10^5\)	\(\le 200\)	\(\le10\)
\(6\)	\(\le 5\)	\(\le 10^5\)	\(\le 3\times 10^6\)	\(2\)
\(7\)	\(\le 5\)	\(\le 10^5\)	\(\le 3\times 10^6\)	\(2\)
\(8\)	\(\le 5\)	\(\le 10^5\)	\(\le 3\times 10^6\)	\(\le10\)
\(9\)	\(\le 5\)	\(\le 10^5\)	\(\le 3\times 10^6\)	\(\le10\)
\(10\)	\(\le 5\)	\(\le 10^5\)	\(\le 3\times 10^6\)	\(\le10\)

决策单调性之 四边形不等式优化（决策单调性优化 dp）¶

[NOI2009] 诗人小G¶

思路¶

[HNOI2008] 玩具装箱¶

[IOI2000] 邮局¶

思路¶

决策单调性之四边形不等式优化（决策单调性优化 dp）¶