题目
思路
谁能想到(O(kn^2))可以过啊qwq
设车到(i)点的时间为(arr_i)，到达(i)点最晚的人的时间为(lat_i)，显然(arr_{i+1} = max(arr_i,lat_i)+d_i)，这样就可以求出来没有用加速器情况下的时间
考虑一个加速器最优的使用方案：要让更多的人的到达时间-1
- 在一条边((i,i+1))上使用加速器，那么(arr_{i+1})会减1，那么到达(i+1)点的所有人时间-1；
- 这还不是全部的贡献，根据上面求(arr)数组的式子，如果(arr_{i+1}>lat_{i+1})，那么(arr_{i+1})减1之后(arr_{i+2})也会减一，还要处理到达(i+2)的所有人......一直循环下去直到(arr<=lat)
每次都找最大贡献的边即可，每次(O(n))找每条边的贡献，时间复杂度为(O(kn^2))，实际上数据比较水完全跑不满
容易发现倒叙枚举边可以(O(n))找到最大贡献的边，从而将复杂度优化至(O(kn))，虽然这道题并不卡这个
Code（正序枚举版本）
#include<bits/stdc++.h>
#define N 10005
#define re register
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,m,k,ans;
int d[N],lat[N],t[N],A[N],B[N];
int dow[N],arr[N];
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
int main()
{
read(n);read(m);read(k);
for(re int i=1;i<n;++i) read(d[i]);
for(re int i=1;i<=m;++i)
{
read(t[i]);
read(A[i]);read(B[i]);
lat[A[i]]=Max(lat[A[i]],t[i]);
++dow[B[i]];
}
arr[1]=0;
for(re int i=1;i<n;++i) arr[i+1]=Max(arr[i],lat[i])+d[i];
while(k--)//枚举加速器
{
int maxnum=0,maxpos=0;
for(re int i=1;i<n;++i)//假设在i~i+1使用加速器
{
if(!d[i]) continue;
int now=0;
for(re int j=i+1;j<=n;++j)
{
now+=dow[j];
if(arr[j]<=lat[j]) break;
}
if(maxnum<now) maxpos=i,maxnum=now;
}
if(!maxpos) break;
--d[maxpos];
for(re int i=maxpos+1;i<=n;++i)//修改
{
--arr[i];
if(arr[i]<lat[i]) break;
}
}
for(re int i=1;i<=m;++i) ans+=(arr[B[i]]-t[i]);
cout<<ans<<endl;
return 0;
}
费用流可做？那个已死的考试不会考的跑的还没暴力贪心快，除了装逼之外没什么实际作用