P10769 「CROI · R2」公交接驳 题解

· · 题解

数轴上有 n 个节点 1\sim n，每个节点有权值 v_i，第 i 个节点和第 i+1 个节点的距离为 s_i。

要求在数轴上安排 k 条路线，指定它的起点和出发时刻（出发时刻可以是负数），它会依次经过编号 \ge 起点的所有点，到达节点 i 的时刻为出发时刻加上起点和节点 i 之间的距离，

要求安排路线后，满足第 i 个节点在 \ge t_i 的时刻有路线经过，设在 \ge t_i 的时刻中最早经过 i 的路线到达节点 i 的时刻为 T_i，该路线的起点权值为 V_i（若多条路线同时到达取最小），则答案为 ans=\sum_{i=1}^n(T_i-t_i)\times V_i，你需要最小化这个值。

你需要处理 p 组 t 数组不同的询问，且对于每个 t 数组，询问 对于 q_i 个 k_i 的答案。

首先因为 s_i\ge t_{i+1}-t_i，所以每条路线产生贡献的节点一定是一个区间。

我们假设 [l,r] 是一条路线产生贡献的极长区间（无法向两边再拓展），那么此时显然每个节点的 T_i-t_i 确定（因为这条路线显然会在 t_l 时刻到达节点 l），然后我们要最小化 V_i，所以取 v_1\sim v_{l} 的前缀最小值。

为了方便表述，我们令 w_i=T_i-t_i,v_i=\max_{j\le i} \{v_j\}。

首先有朴素 dp，令 f_{i,j} 表示前 i 个点已经被贡献区间覆盖，且安排了 j 条路线的最小贡献。

我们枚举上一个贡献区间的终点 k，有 f_{i,j}=\min\{f_{k,j-1}+val_{k+1,i}\}，val_{l,r}=v_l\cdot \sum_{i=l}^r w_i。

我们观察转移式子，假设 $i-1$ 的转移点为 $q$， 则 $\forall p<q$，满足 $f_{q,j-1}+val_{q+1,i-1}\le f_{p,j-1}+val_{p+1,i-1}$。 然后 $i$ 从 $p,q$ 转移的式子分别为 $f_{q,j-1}+val_{q+1,i}$ 和 $f_{p,j-1}+val_{p+1,i}$。 显然有 $\begin{cases} val_{q+1,i}-val_{q+1,i-1}=v_{q+1}\cdot w_i\\val_{p+1,i}-val_{p+1,i-1}=v_{p+1}\cdot w_i\end{cases}

然后因为 v_i 是前缀最小值所以 v_{q+1}\le v_{p+1}。

显然左式比右式增速慢，于是左式永远优于右式，所以随着 i 的增加，f_{i,j} 的最优转移点单调不降，即 f_{i,j} 具有决策单调性。

所以我们以 j 分层，然后对于每一层进行决策单调性分治，可以在 \mathcal{O}(n\log n) 的时间内完成单层转移。

时间复杂度 \mathcal{O}(n^2\log n)，然后对于 p 组 t 的数据都要重新跑 dp，则总时间复杂度 \mathcal{O}(qn^2\log n)。

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<ll,ll>
using namespace std;
const ll MAXN = 1e3 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;

ll n,q;
ll s[MAXN],v[MAXN];
ll t[MAXN],pre[MAXN];
ll val[MAXN][MAXN];
ll f[MAXN],g[MAXN],pos[MAXN];
ll ans[MAXN]; 

void solve(ll l,ll r,ll L,ll R){
    if(l>r) return ;
    if(L==R){
        FL(i,l,r) g[i]=f[L]+val[L+1][i];
        return ;
    }
    ll mid=(l+r)>>1;
    FL(i,max(pos[mid],L),min(mid-1,R))
        if(f[i]+val[i+1][mid]<g[mid])
            g[mid]=f[i]+val[i+1][mid],pos[mid]=i;
    solve(l,mid-1,L,pos[mid]);
    solve(mid+1,r,pos[mid],R);
}

signed main(){
    freopen("bus.in","r",stdin);
    freopen("bus.out","w",stdout); 
    scanf("%lld",&n);
    FL(i,1,n-1) scanf("%lld",&s[i]);
    FL(i,1,n) scanf("%lld",&v[i]);
    FL(i,2,n) v[i]=min(v[i],v[i-1]);
    ll Num;
    scanf("%lld",&Num);
    while(Num--){
        FL(i,1,n) scanf("%lld",&t[i]);
        FL(i,1,n-1) pre[i]=pre[i-1]+(s[i]-(t[i+1]-t[i]));
        FL(i,1,n)
            FL(j,i+1,n)
                val[i][j]=val[i][j-1]+v[i]*(pre[j-1]-pre[i-1]);
        FL(i,0,n) f[i]=g[i]=inf,pos[i]=0;
        f[0]=0;
        FL(k,1,n){
            solve(1,n,0,n-1);
            FL(j,1,n) f[j]=g[j],g[j]=inf;
            ans[k]=f[n];
        }
        scanf("%lld",&q);
        while(q--){
            ll k;
            scanf("%lld",&k);
            printf("%lld ",ans[min(n,k)]);
        }
        puts("");
    }
}