题解：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)，写得好看的话过掉还是比较简单的。

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

// 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记录