joisc2017 D3T1 长途巴士 题解
这是学校 ACM 欢乐赛的题，赛时想到做法了，但是因为我各种唐诗没写出来
翻了
转化题面
我们发现，只可以踢掉检查站前面一个连续段的接水人，并且不能踢掉司机，考虑画出对整个路程表示的线段
上图几个小点是检查点，考虑在每个检查点之前踢掉一段的人，容易发现不能踢掉司机，后踢掉一个人一定不如在前面踢掉他优，所以区间没有交
考虑预处理出每个检查点踢掉每个人能节省的水费，直接 dp 即可，然而问题在于本题 \(10^{12}\) 的决策数
我们发现其实我们只关心踢掉哪些人和省了多少水，第二个已经预处理出来了，所以我们将人按照 \(D_i\) 排序，同样每次决策只会选择后面的一段，把 \(S_i \mod t\) 同时排序，发现其实贡献可以拆成两个部分，分别是
- 右端点（即检查点）的权值，也就是踢掉每个人的水费减少量
- 其他点的权值，也就是踢掉一个人要退的钱
暴力
我们容易写出转移方程
\[dp_i=\min_{1 \le k \le i}((k-pl_i-1)p_i+dp_{f(k)}+g(k,pl_i),dp_{i-1}) \]稍微解释一下，\(f(x)\) 表示在 \(x\) 前面的第一个决策点，直接预处理。\(g(x,y)\) 表示将所有 $ x \le D \le y$ 的全部人赶下车要得到的钱，\(pl_i\) 是第 \(i\) 个决策点的位置，\(p_i\) 是能省的钱
发现可以预处理后缀和算 \(g(x,y)\)，同时我们为了避免之后 dp 过程中用 $x \mod t $ 与 \(k\) 分讨，也把这个扔进去。
把一个人都不踢的钱和最后的 dp 值相加即为答案
复杂度 \(O(n^2)\)
优化
斜率优化板子
当做斜率优化笔记写吧
把式子展开，发现长这个样子（\(c\) 是后缀和）
\[dp_i=kp_i-pl_ip_i-p_i+dp_{f(k)}+c_k-c_{pl_i+1} \]只有右边最前面那个是关于 \(i\)，\(k\) 一次函数的乘积项，显然可以斜率优化
按照那个式子移个项
\[c_{pl_i+1}+pl_ip_i+p_i+dp_i-kp_i=dp_{f(k)}+c_k \]固定 \(i\)，左边那一坨都是定值，为了最小化 \(dp_i\)，最小化那一整坨就完了，所以我们维护一个斜率单调递增的下凸壳，注意斜率是 \(p_i\)，我们之前为了让 \(pl_i\) 有序，从而确定 dp 顺序，所以将决策排序了，\(p_i\) 被打乱了，并不单调，要在单调栈里面二分
代码
点击查看代码
#include<bits/stdc++.h>
#define llt long long
#define llb long double
using namespace std;
const llt N=200010;
llt x,n,m,w,t,d[N],c[N],s[N],pl[N],p[N],f[N],dp[N],us,siz,sum,ans,tot,X[N],y[N],P,xx,yy,head=1,tail,last;
pair<llt,llt> pr[N],pi[N];
llb calc(llb xa,llb ya,llb xb,llb yb){return (yb-ya)/(xb-xa);}
llt find(llb K)
{
llt l=head,r=tail,mid;
while(l<r)
{
mid=l+r>>1;
if(calc(X[mid],y[mid],X[mid+1],y[mid+1])<K)
l=mid+1;
else r=mid;
}
return l;
}
int main()
{
#ifdef LOCAL
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t);
for(int i=1;i<=n;i++) scanf("%lld",&s[i]);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld",&pr[i].first,&pr[i].second);
if(x%t>=pr[i].first) sum+=1+x/t;
else sum+=x/t;
}
sum+=x/t+1;
ans=sum*w;
for(int i=1;i<=n;i++){pl[i]=s[i]%t,p[i]=x/t*w-(s[i]/t)*w;}
pl[++n]=x%t;p[n]=0;sort(pr+1,pr+1+m);
for(int i=1;i<=n;i++) pl[i]=upper_bound(pr+1,pr+1+m,make_pair(pl[i],0ll))-pr-1;
for(int i=1;i<=n;i++) pi[i]=make_pair(pl[i],p[i]);
sort(pi+1,pi+1+n);
for(int i=1;i<=m;i++) d[i]=pr[i].first,c[i]=pr[i].second;
for(int i=1;i<=m;i++) if(d[i]<=x%t) c[i]-=w;
for(int i=m;i>=1;i--) c[i]=c[i+1]+c[i];
for(int i=1;i<n;i++)
{
if(pi[i].first==pi[i+1].first) continue;
pl[++siz]=pi[i].first;
p[siz]=pi[i].second;
}
pl[++siz]=pi[n].first;p[siz]=pi[n].second;
for(int i=0;i<=siz;i++)
for(int j=pl[i]+1;j<=pl[i+1];j++)
f[j]=i;
P=1;while(pl[P]==0) P++;
for(int i=1;i<=m;i++)
{
xx=i,yy=dp[f[i]]+c[i];
while(head<tail&&calc(X[tail-1],y[tail-1],X[tail],y[tail])>=calc(X[tail],y[tail],xx,yy)) tail--;
X[++tail]=xx,y[tail]=yy;
if(i==pl[P]) {us=find(-p[P]);dp[P]=y[us]-c[pl[P]+1]-pl[P]*p[P]-p[P]+p[P]*X[us];dp[P]=min(dp[P],dp[P-1]);P++;}
}
cout<<dp[siz]+ans<<endl;
return 0;
}