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

· · 题解

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

题面大意

传送门。

解题思路

非常典的斜率优化。

居民们肯定是去离他们最近，且可以到达的集会点，否则一定不优。

根据题面的 d_i 和 t_i 推导出到起点距离为 i 处的人数 s_i。

记 f_{i,t}(0\le i\le l,0\le t\le 4) 为在离起点距离为 i 处建第 t 个集合点的最小花费。特别地，我们认为 f_{0,0},f_{1,0},\cdots,f_{n,0}=0。

可得以下的状态转移方程：

f_{i,t}=\min\{f_{j,t-1}+(i-j-1)\cdot s_{j+1}+(i-j-2)\cdot s_{j+2}+\cdots+(i-i)\cdot s_i\}(j\le i)

按上述状态转移方程搞一个暴力转移，时间复杂度为 O(l^3)（完全暴力处理）或 O(l^2)（继承答案优化），可以分别获得 10pts 或 30pts。

考虑对上式进行斜率优化。

变换式子，得：

f_{i,t}=\min\{f_{i,t-1}+i\cdot(s_{j+1}+s_{j+2}+\cdots)-((j+1)\cdot s_{j+1}+(j+2)\cdot s_{j+2}+\cdots+i\cdot s_i)\}

记 sum1_i=s_0+s_1+\cdots+s_i,sum2_i=0\cdot s_0+1\cdot s_1+\cdots+i\cdot s_i，可将继续变换为前缀和的形式：

f_{i,t}=\min\{f_{j,t-1}+i\cdot(sum1_i-sum1_j)-(sum2_i-sum2_j)\}

去掉括号，写成斜优的标准形式如下：

f_{i,t}=\min\{-sum1_j\cdot i+sum2_j+f_{j,t-1}\}+i\cdot sum1_i-sum2_i

令 k=-sum1_j，x=i，b=sum2_j+f_{j,t-1}，原问题就变为：求若干条形如 y=kx+b 的直线，求横坐标为 x 时纵坐标最小的那条。

使用李超线段树（LCT）维护即可。

最后的答案即为 f_{l,4}。

编写代码时，可以让 f_{i,t} 从任意的 f_{j,t-1} 转移，无需满足 j\le i 的条件，因为变换集会点的顺序不会影响最终答案。

参考代码

#include<algorithm>
#include<iostream>
using namespace std;
#define s sum1
#define int long long
const int N=1e6+10;
const int INF=0x7fffffff;
struct node{
    int l,r,bst;
}tree[4*N];
struct ccf{
    int k,b;
}ln[N];
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    if(lft==rgt) return;
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
}
void upd(int pos,int num){
    int mid=(tree[pos].l+tree[pos].r)/2;
    if((ln[tree[pos].bst].k==ln[num].k)&&(ln[tree[pos].bst].b==ln[num].b)) return;
    if(ln[tree[pos].bst].k*mid+ln[tree[pos].bst].b>ln[num].k*mid+ln[num].b) swap(tree[pos].bst,num);
    if(tree[pos].l==tree[pos].r) return;
    if(ln[num].k*tree[pos].l+ln[num].b<ln[tree[pos].bst].k*tree[pos].l+ln[tree[pos].bst].b) upd(pos*2,num);
    if(ln[num].k*tree[pos].r+ln[num].b<ln[tree[pos].bst].k*tree[pos].r+ln[tree[pos].bst].b) upd(pos*2+1,num);
}
int ask(int pos,int kk){
    if(kk<tree[pos].l||tree[pos].r<kk) return INF;
    if(tree[pos].l==tree[pos].r) return ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b;
    return min(min(ask(pos*2,kk),ask(pos*2+1,kk)),ln[tree[pos].bst].k*kk+ln[tree[pos].bst].b);
}
int n,l,cnt;
int sum1[N],sum2[N],f[N];
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>l;
    while(n--){
        int dd,tt;
        cin>>dd>>tt;
        s[dd]+=tt; 
    }
    for(int i=1;i<=l;i++){
        sum2[i]=sum2[i-1]+s[i]*i;
        s[i]+=s[i-1];
    }
    ln[0].b=INF;
    build(1,0,l);
    ln[++cnt]={0,0};
    upd(1,cnt);
    for(int i=1;i<=3;i++){
        for(int j=0;j<=l;j++){
            f[j]=ask(1,j)+sum1[j]*j-sum2[j];
        }
        build(1,0,l);
        cnt=0;
        for(int j=0;j<=l;j++){
            ln[++cnt]={-sum1[j],sum2[j]+f[j]};
            upd(1,cnt);
        }
    }
    cout<<ask(1,l)+sum1[l]*l-sum2[l];
    return 0;
}

此代码可以通过洛谷评测。

Written by toolong114514 on 2024/6/12.