P5896 [IOI2016]aliens

Alex_Wei · 2021-07-09 18:02:32 · 题解

*IX. P5896 [IOI2016]aliens

DP 优化方法大杂烩，详解 wqs 二分及其注意事项，斜率优化等其它 DP 优化方法。

更好的阅读体验。

**** 团队赛 T6，没想到是 IOI 原题。当时看出来要用 wqs 二分，但是我没学过（经常发生知道要用某种算法但是不会写的情况），因此最近学习了一下 wqs 二分。找题目练手的时候看到了这题，世界线收束。做题的过程中发现还要用到斜率优化，于是也学了一下。

这算是一道比较套路的题目，但套路并不意味这不是好题，毕竟我从中学到了 wqs 二分和斜率优化两种 DP 优化方法。说它套路其实也不太合适，因为 2016 年 wqs 二分还没有在 OI 界普及，甚至国外将其称之为 “Aliens’ Trick” 就是根据本题的名字而命名的，所以这个 idea 在当时应该比较新颖。

不妨对网格图的主对角线所经过的格子从左上到右下依次编号为 0,1,2,\cdots,m-1。显然，编号为 i 的格子在原网格图中的坐标为 (i,i)。因为正方形的主对角线完全包含于网格图的主对角线，所以为了拍到一个点 (r_i,c_i) 必然要拍到编号为 l_i,l_i+1,l_i+2,\cdots,r_i 的格子，其中 l_i=\min(r_i,c_i),r_i=\max(r_i,c_i)。因此，我们可以将题目转化为线段覆盖问题：现在有 n 条线段 [l_i,r_i]，我们要用最多 k 个区间 [x_i,y_i] 去覆盖它们，使得每条线段至少被一个区间完全包含。即 \forall i,\exist j,s.t. [l_i,r_i]\in [x_j,y_j]。求以每个区间为对角线形成的所有正方形的面积并的最小值。接下来我们可以挖掘一些性质：

正确性显然。根据该性质，我们可以将所有线段按照左端点 $l_i$ 从小到大为第一关键字，右端点 $r_i$ 从大到小为第二关键字排序。然后依次遍历所有线段并记录右端点最大值 $r$。若当前线段 $i$ 的右端点 $r_i\leq r$，则忽略线段 $i$；否则用 $r_i$ 去更新 $r$，即 $r\gets r_i$。最终所有没有被忽略的线段，一定满足**左端点和右端点都单调递增**。读者自证不难。
读者自证不难。
读者自证~~不~~很难。感性理解一下即可，严格证明的话应该比较复杂。

有了上述性质，我们可以愉快地进行 DP 了：wqs 二分斜率 K，然后设 f_i 表示覆盖第 i 条线段时的最小代价（线段按照左端点从小到大排序。根据性质 1 的结论，右端点也行，因为不影响线段之间的顺序）。显然有转移方程：

f_i=\min_{j=0}^{i-1}-K+\begin{cases}f_j+(y_i-x_{j+1}+1)^2-(y_j-x_{j+1}+1)^2&y_j\geq x_{j+1}\land j>0\\f_j+(y_i-x_{j+1}+1)^2&\mathrm{otherwise}\end{cases}

这个分情况讨论很讨厌，尝试把它消灭掉：设 g_i=(y_i-x_{i+1}+1)^2[y_i\geq x_{i+1}\land i>0]，那么转移方程变为 f_i=\min_{j=0}^{i-1}f_j+(y_i-x_{j+1}+1)^2-g_j-K。显然的斜率优化，~~但是我不会~~，所以多讲一点：拆开变成 f_i=\min_{j=1}^{i-1} f_j+(y_i+1)^2-2(y_i+1)x_{j+1}+x^2_{j+1}-g_j-K。先将所有 y_i 加上 1（不影响单调性），忽略掉 \min 再移移项，写成 Y=kX+b 的形式，f_j+x^2_{j+1}-g_j-K=2y_ix_{j+1}+(f_i-y_i^2)。那么 Y=f_j+x^2_{j+1}-g_j-K，k=2y_i，X=x_{j+1}，b=f_i-y^2_i。将 (X_j,Y_j) 看做一个点，因为 k 确定了，现在就要找使得 b 最小的 (X_j,Y_j)（这样能使得 f_i 最小）。由于 k,X 都是单调递增的，所以单调队列维护下凸包即可。

具体地，记 k_{i,j} 为点 (X_i,Y_i) 与 (X_j,Y_j) 之间的斜率。首先将点 0 加入单调队列，接下来遍历从小到大每个位置 i：

若单调队列大小不小于 2，设 a,b 分别为队首的第一个和第二个点，若 k_{a,b}\leq k=2y_i 则 b 一定不劣于 a，弹出队首。重复该操作直到单调队列大小为 1 或 k_{a,b}>2y_i。
此时队首 a 即为最优决策 j，f_j\to f_i 转移并记录选择的区间个数。
若单调队列大小不小于 2，设 c,d 分别为队尾的倒数第二个和倒数第一个点；若 k_{c,d}\geq k_{d,i} 则 d 一定不在下凸包上，弹出队尾。重复该操作直到单调队列大小为 1 或 k_{c,d}<k_{d,i}。
将点 i 加入单调队列。

我们需要求出在代价最小的前提下最少的区间个数。不妨设 num_i 为覆盖前 i 条线段且代价最小时最少的区间个数，那么因为 num_i 显然有单调性，所以我们每次转移时只需要选择最前面的一个决策点转移即可，即第一步操作弹出队首时，将条件 k_{a,b}\leq 2y_i 改为 k_{a,b}<2y_i，这样就保证了相同优劣的决策点，前者不会被后者所弹出（第三步的条件不需要改，因为是前面的决策点弹出后面的决策点，不影响结果）。

时间复杂度 \mathcal{O}(n\log V)，其中 V 是二分范围，本题中为 m^2。浮点数比较建议使用 eps。代码倒是不难写。

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

#define ll long long
#define ld long double

const int N=1e5+5;
const ld eps=1e-10;

ll n,m,k,c,ans;
struct seg{
    int l,r;
    bool operator < (const seg &v) const{
        return l!=v.l?l<v.l:r>v.r;
    }
}p[N];

ll K,f[N],g[N],num[N];
ll sq(ll x){return x*x;}
ll Y(int i){return f[i]+sq(p[i+1].l)-g[i]-K;}
ll X(int i){return p[i+1].l;}
ld slope(int i,int j){return (ld)(Y(j)-Y(i))/(X(j)-X(i));}

ll hd,tl,d[N];
bool check(){
    d[hd=tl=1]=0;
    for(int i=1;i<=n;i++){
        while(hd<tl&&slope(d[hd],d[hd+1])+eps<=2*p[i].r)hd++;
        int j=d[hd]; num[i]=num[j]+1,f[i]=f[j]+sq(p[i].r-p[j+1].l)-g[j]-K;
        if(i<n)while(hd<tl&&slope(d[tl-1],d[tl])-eps>=slope(d[tl],i))tl--;
        d[++tl]=i;
    } return num[n]<=k;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1,c,r;i<=n;i++){
        cin>>p[i].l>>p[i].r;
        if(p[i].l>p[i].r)swap(p[i].l,p[i].r);
    } sort(p+1,p+n+1);
    for(int i=1,r=-1;i<=n;i++)if(p[i].r>r)r=p[i].r,p[++c]=p[i]; n=c;
    for(int i=1;i<n;i++)if(p[i].r>=p[i+1].l)g[i]=sq(p[i].r-p[i+1].l+1);
    for(int i=1;i<=n;i++)p[i].r++;
    ll l=-1e12,r=0;
    while(l<r)K=(l+r>>1)+1,check()?(l=K,ans=f[n]+K*k):r=K-1;
    cout<<ans<<endl;
    return 0;
}