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

· · 题解

首先把道路的终点也看做一个家庭，这个家庭的人数是 0，到达公路起点的距离就是 L。

设 dp_{i,j} 为在第 i 户家庭修建第 j 个集会地点，前 i 户的开销之和的最小值，最终答案就是 dp_{n+1,4}。可以在开始的时候直接选择将 n 加上 1，最后输出 dp_{n,4}。

状态转移方程：dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+\sum\limits_{p=k+1}^{i}(t_p\times(d_i-d_p)))，在这之前要先将 dp 初始化为无穷大。

显然如果直接这样做会直接 T 飞，所以考虑优化。

一个显而易见的优化是使用前缀和，设 st_i=\sum\limits_{p=1}^{i}t_p，std_i=\sum\limits_{p=1}^{i}(t_p\times d_p)，那么原状态转移方程就能写为：dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+d_i\times(st_i-st_k)-(std_i-std_k))，拆括号并整理得到 dp_{i,j}=\min\limits_{k=0}^{i-1}(dp_{k,j-1}+std_k-d_i\times st_k+d_i\times st_i-std_i)。

为什么要这么整理呢？因为不难发现在本题的情况下，决策单调性是显然的，将转移式改成 y=kx+b 的形式，就可以用斜率优化 dp。

去除 \min 并将转移式改写成 dp_{k,j-1} + std_k = d_i\times st_k + std_i - d_i\times st_i + dp_{i,j}，并令：

y=dp_{k,j-1} + std_k k=d_i x=st_k b=std_i - d_i\times st_i + dp_{i,j}

要让 dp_{i,j} 最小，则要 b 最小，单调队列维护下凸壳即可。

具体在 dp 的时候要先推一遍 j=1 的情况。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
/*
dp[i][j] 在第 i 户家庭修建第 j 个集会地点，前 i 户的开销最小值
dp[i][j] = min[k=0,i-1](dp[k][j-1]+sum[p=k+1,i](t[p]*(d[i]-d[p])))
dp[i][j] = min[k=0,i-1](dp[k][j-1]+sum[p=k+1,i](t[p]*d[i])-sum[p=k+1,i](t[p]*d[p]))
dp[i][j] = min[k=0,i-1](dp[k][j-1] + sum[p=k+1,i]t[p]*d[i] - sum[p=k+1,i](t[p]*d[p]))
设 st[i] = sum[p=1,i](t[p]), std[i] = sum[p=1,i]t[p]*d[p]
dp[i][j] = min[k=0,i-1](dp[k][j-1] + (st[i]-st[k])*d[i] - (std[i]-std[k]))
dp[i][j] = min[k=0,i-1](dp[k][j-1] + st[i]*d[i] - st[k]*d[i] - std[i] + std[k]) 注：st[i]*d[i] 不等于 std[i]
dp[k][j-1] + st[i]*d[i] - st[k]*d[i] - std[i] + std[k] - dp[i][j] = 0
dp[k][j-1] = - st[i]*d[i] + st[k]*d[i] + std[i] - std[k] + dp[i][j]
dp[k][j-1] + std[k] = d[i]*st[k] + std[i] - st[i]*d[i] + dp[i][j]
y                   = k    x     + b
求最小维护下凸壳 
*/
int n,L,d[N],t[N],dp[N][5],st[N],st_d[N],q[N];
double K(int p1,int p2,int j){
    double xp1=st[p1];
    double xp2=st[p2];
    double yp1=dp[p1][j-1]+st_d[p1];
    double yp2=dp[p2][j-1]+st_d[p2];
    return (yp2-yp1)/((xp2-xp1==0)?1e-9:xp2-xp1);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>L;
    for(int i=1;i<=n;i++)cin>>d[i]>>t[i];
    d[++n]=L;t[n]=0;
    for(int i=1;i<=n;i++)st[i]=st[i-1]+t[i],st_d[i]=st_d[i-1]+t[i]*d[i];
    //初始化 j=1 的情况
    for(int j=1;j<=1;j++){
        for(int i=1;i<=n;i++){
            dp[i][j]=dp[i-1][j]+(d[i]-d[i-1])*st[i-1];//将前面所有 st[i-1] 个人全部迁移 (d[i]-d[i-1]) 的长度 
        }
    } 
    for(int j=2;j<=4;j++){
        for(int i=0;i<=n;i++)q[i]=0;
        for(int i=0;i<=n;i++)dp[i][j]=(1ll<<60);
        int h=1,aqua=0;
        for(int i=1;i<=n;i++){
            while(h<aqua&&K(q[aqua-1],q[aqua],j)>=K(q[aqua-1],i-1,j))aqua--;
            q[++aqua]=i-1;
            while(h<aqua&&K(q[h],q[h+1],j)<=d[i])h++;
            int k=q[h];
            dp[i][j]=dp[k][j-1]+st[i]*d[i]-st[k]*d[i]-st_d[i]+st_d[k];
        }
    }
    cout<<dp[n][4];
    return 0;
}