自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:15:23，当前版本为作者最后更新于2025-08-04 09:07:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

:::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;
}

:::