P5896 [IOI 2016] aliens

· · 题解

这是我第一道不看题解做出正解的黑题！实现细节与所有题解均不同！

:::info[喜提洛谷当前最优解] 精细实现一下抢到了最优解 https://www.luogu.com.cn/record/228655964。 :::

:::warning[Hint]{open} 考虑一个正方形可以覆盖一个兴趣点 (u,v) 的充要条件。出于对称性，不妨令 u\le v。同时设该正方形的左上角方格为 (l,l)，右下角方格为 (r,r)，则充要条件为 l\le u\le v\le r。

注意到我们所选取的 (l,r) 一定互不包含，同时有 l\in\{u\} 且 r\in\{v\}，否则一定不优。

自此，转化为区间覆盖问题。

同时结合题目中对拍摄次数的限制，不难想到是 wqs 二分套斜率优化 DP。 :::

我们令 p_i=\displaystyle\min_{v=i}(u)，dp_i 为当前区间右端点为 i 时被拍摄到的小方格数量的最小值，wqs 二分出的斜率为 \text{mid}。

则状态转移方程为：

dp_i=\text{mid}+\min_{j=0}^{i-1}(dp_j+(i-\min_{k=j+1}^{i}p_k+1)^2-\max(0,j-\min_{k=j+1}^{i}p_k+1)^2)

再次利用所选区间互不包含的性质，我们将 \displaystyle\min_{k=j+1}^{i}p_k 改为 \displaystyle\min_{k=j+1}^{m}p_k 并设为 pos_j，同时稍作整理：

dp_i=\text{mid}+i^2+2i+1+\min_{j=0}^{i-1}(y_j-2i\cdot pos_j)

其中 y_j=dp_j+pos_j^2-2pos_j-\max(0,j-pos_j+1)^2。

时间复杂度 \mathcal{O}(m+n\log m)，空间复杂度 \mathcal{O}(n+m)。

:::warning[维护下凸壳时的易错点]{open} 注意到此题中横坐标 pos_j 非降，并不保证单调递增。

所以一定要注意决策点重合的情况。 :::

:::success[[IOI 2016] aliens - P5896.cpp]{open}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5,maxm=1e6+5;
int pos[maxm],vis[maxm],sta[maxn],cnt[maxn],n,m,k,top;
ll py[maxn],pre[maxn],dp[maxn];
inline ll squ(ll val){return val*val;}
inline bool check(int u,int v,int w){
    return (py[v]-py[u])*(pos[w]-pos[v])>=(py[w]-py[v])*(pos[v]-pos[u]);
}
inline void solve(ll mid){
    int pl=1,pr=1;
    py[0]=pre[0];
    for(int i=1;i<=top;++i){
        while(pl<pr and (py[sta[pl+1]]-py[sta[pl]])
        <2ll*vis[i]*(pos[sta[pl+1]]-pos[sta[pl]])) ++pl;

        dp[i]=py[sta[pl]]-2ll*vis[i]*pos[sta[pl]]+squ(vis[i]+1)+mid;
        cnt[i]=cnt[sta[pl]]+1;
        py[i]=dp[i]+pre[i];
        while(pl<pr and check(sta[pr-1],sta[pr],i)) --pr;
        sta[++pr]=i;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>k;
    int u,v;
    for(int i=0;i<=m;++i) pos[i]=1e9;
    for(int i=1;i<=n;++i){
        cin>>u>>v;
        ++u,++v;
        if(u>v) swap(u,v);
        pos[v-1]=min(pos[v-1],u);
        vis[v]=1;
    }
    for(int i=m-1;i>=0;--i) pos[i]=min(pos[i],pos[i+1]);
    for(int i=1;i<=m;i++) if(vis[i]) vis[++top]=i;
    for(int i=0;i<=top;i++){
        pos[i]=pos[vis[i]];
        pre[i]=1ll*pos[i]*pos[i]-2*pos[i]-squ(max(0,vis[i]-pos[i]+1));
    }
    ll l=0,r=1ll*m*m,mid,res=0;
    while(l<=r){
        mid=(l+r)>>1;
        solve(mid);
        if(cnt[top]<=k) res=mid,r=mid-1;
        else l=mid+1;
    } 
    solve(res);
    cout<<(dp[top]-k*res)<<"\n";
    return 0;
}

:::