题解：P8632 [蓝桥杯 2015 国 B] 居民集会

YZren · 2025-04-22 16:03:49 · 题解

题目传送门

思路

• 可以发现此题与仓库建设很像，没做过的可以去做一下。

• 回到这道，令 sumnum_i=\sum\limits_{k=0}^i d_k 和 sum_i=sum_{i-1}+sumnum_{i-1} 其中 sumnum_i 表示到 i 这个位置共有多少人，然后 sum_i 表示 i 以前的人到 i 的总距离。可以得出一个 Dp 方程 dp_{i,t}=\min\limits_{k=0}^i(dp_{k,t-1}+sum_i-sum_k-sumnum_k\times (i-k))。可以发现直接枚举肯定要超时，但是整理一下方程可得 dp_{i,t}=sum_i+\min\limits_{k=0}^i(-sumnum_k\times i+sumnum_k\times k-sum_k+dp_{k,t-1}) 可以发现很像一个一次函数，所以使用斜率优化。

• 使用李超线段树维护最小值即可。

Code

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define F(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
const int maxn=1e6+10,inf=LLONG_MAX;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) {x=~(x-1); putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n=read(),L=read(),root=1,dp[maxn][5],sum[maxn],sum_num[maxn],dis[maxn/10],tree[maxn<<2];
struct line{int k,b;} a[maxn];
inline int getY(int id,int X){return a[id].k*X+a[id].b;}
inline void update(int rt,int l,int r,int id){
    if(l==r){
        if(getY(id,l)<getY(tree[rt],l)) tree[rt]=id;
        return ;
    }
    int mid=(l+r)>>1;
    if(getY(id,mid)<getY(tree[rt],mid)) swap(tree[rt],id);
    if(getY(id,l)<getY(tree[rt],l)) update(rt<<1,l,mid,id);
    else if(getY(id,r)<getY(tree[rt],r)) update(rt<<1|1,mid+1,r,id);
}
inline int query(int rt,int l,int r,int X){
    if(!rt) return inf;
    if(l==r) return getY(tree[rt],X);
    int mid=(l+r)>>1;
    if(X<=mid) return min(getY(tree[rt],X),query(rt<<1,l,mid,X));
    else return min(getY(tree[rt],X),query(rt<<1|1,mid+1,r,X));
}
inline void work(){
    update(root,0,L,L+1); f(i,1,n) dis[i]=read(),sum_num[dis[i]]+=read();
    f(i,1,L) sum_num[i]+=sum_num[i-1],sum[i]=sum[i-1]+sum_num[i-1];
    f(j,1,4){
        f(i,1,L) dp[i][j]=query(root,0,L,i)+sum[i];
        memset(tree,0,sizeof(tree)); root=1; update(root,0,L,L+1); 
        f(i,1,L) a[i]=(line){-sum_num[i],sum_num[i]*i-sum[i]+dp[i][j]}, update(root,0,L,i);
    } write(dp[L][4]);
}
signed main(){work();return !!!!!("YZren");}