题解：CF311B 猫咪运输

看见题解区没有用李超树的，我当然要来水水咕值了。

一道很不错的二维斜率优化。

先处理出每个小猫需要在什么时候出发才能恰好能够接走这只小猫，设为

a_i

。对于一组小猫，饲养员需要在最晚的那一只小猫的时间出发，否则他就无法接到某些小猫。

我们有一个非常显然的贪心：将

a

数组从小到大排序，一个饲养员所接的小猫的

a

的值必定是连续的。所以我们可以对

a

数组进行 dp。

套路的，我们先写暴力的 dp 式子。设

dp_{i,j}

表示现在已经派出去了

i

个饲养员，且已经处理了前

j

只猫时的最少等待时间。

dp_{i,j}=\displaystyle \min _{t=0}^{j-1}\{dp_{i-1,t}+a_j\times (j-t)-(sum_j-sum_t)\}

然后，让我们把它完全展开以方便优化。

dp_{i,j}=dp_{i-1,t}+a_j\times j-a_j \times t-sum_j+sum_t

我们发现其中只有一项同时和

j

与

t

两个变量相关，很明显的斜率优化。我们把它美化一下。

dp_{i,j}=-a_j \times t＋dp_{i-1,t}+sum_t+a_j\times j-sum_j

这个时候斜率优化的式子就很明显了，令

y=dp_{i,j},k=-t,x=a_j,b=dp_{i-1,t}+sum_t

，那它就是函数取最值，可以使用李超树维护。

什么？你问我时间复杂度？复杂度是

O(m\times p \times \log_2m)

，写得好看的话过掉还是比较简单的。

下面给出我的实现并不精细的代码。

CPP

// Problem: B. Cats Transport
// Contest: Codeforces - Codeforces Round 185 (Div. 1)
// URL: https://codeforces.com/problemset/problem/311/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: Binah_cyc

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=1e5+5;
int n,m,q,a[N],sum[N];
vector<int> b;

struct Segment
{
	int k,b;
	int operator()(int x){return k*::b[x]+b;}
	Segment(int _k=0,int _b=LLONG_MAX>>2){k=_k,b=_b;}
}t[N<<2];
void change(Segment id,int tl,int tr,int p)
{
	int mid=(tl+tr)>>1;
	if(t[p](mid)>id(mid)) swap(t[p],id);
	if(t[p](tl) >id(tl) ) change(id,tl,mid,p<<1);
	if(t[p](tr) >id(tr) ) change(id,mid+1,tr,p<<1|1);
}
int ask(int x,int tl,int tr,int p)
{
	int ans=LLONG_MAX;
	while(1)
	{
		ans=min(ans,t[p](x));
		if(tl==tr) return ans;
		int mid=(tl+tr)>>1;
		if(x<=mid) tr=mid,p<<=1;
		else tl=mid+1,p=p<<1|1;
	}
}
void clear(int tl,int tr,int p)
{
	t[p]={0,LLONG_MAX>>2};
	if(tl==tr) return ;
	int mid=(tl+tr)>>1;
	clear(tl,mid,p<<1),clear(mid+1,tr,p<<1|1);
}
//李超树板子
int dp[N][105];

main()
{
	cin.tie(0)->sync_with_stdio(false);
	cin>>n>>m>>q;
	for(int i=2;i<=n;i++) cin>>sum[i],sum[i]+=sum[i-1];
	for(int i=1,x,y;i<=m;i++) cin>>x>>y,a[i]=y-sum[x];
	sort(a+1,a+m+1);
	for(int i=1;i<=m;i++) sum[i]=sum[i-1]+a[i];
	//求出a和前缀和sum
	
	b.push_back(LLONG_MIN);
	for(int i=1;i<=m;i++) b.push_back(a[i]);
	sort(b.begin(),b.end()),b.erase(unique(b.begin(),b.end()),b.end());
	//离散化
	
	for(int i=1;i<=m;i++) dp[1][i]=a[i]*i-sum[i];
	int lim=b.size()-1;
	for(int i=2;i<=q;i++)
	{
		clear(1,lim,1);//先把树给清干净
		for(int j=0;j<=m;j++) change({-j,dp[i-1][j]+sum[j]},1,lim,1);//保证dp[i][j]的前导状态是dp[i-1][t]
		for(int j=1;j<=m;j++) dp[i][j]=ask(lower_bound(b.begin(),b.end(),a[j])-b.begin(),1,lim,1)+j*a[j]-sum[j];//照着式子写一遍就行
	}
	cout<<dp[q][m];
	return 0;
}

AC记录

题解：CF311B 猫咪运输

文章操作

相关推荐

评论

题解：CF311B 猫咪运输