https://codeforces.com/contest/1101/problem/F
题意
有n个城市,m辆卡车,每辆卡车有起点(s_i),终点(f_i),每公里油耗(c_i),可加油次数(r_i),每辆卡车的油箱大小一样,每次加油都会加满,在城市之间不能加油,问最小油箱大小能满足每辆卡车顺利到达终点
题解
- n<=400,m<=250000,考虑离线处理出任意两个城市能加油k次的最小油耗,然后对于每辆卡车询问
- 定义dp[l][r][k]为区间[l,r]能分成(k+1)段各段的最小值
- (dp[l][r][k]=min(max(dp[l][i][k-1],a[r]-a[i])),l leq i leq r),(O(n^4)),会超时
- 观察一下,(dp[l][i-1][k-1]leq dp[l][i][k-1]),((a[r]-a[i-1]) geq (a[r]-a[i]))
- 即随着i的增加,max()的左边越来越大,右边越来越小,那么min()的点一定在(dp[l][i][k-1])和(a[r]-a[i])最接近的时候,队列维护一下,(O(n^3))
- 然后滚掉第一维,空间((n^2)),对于每个(s_i)离线处理
- 注意dp初始化问题
代码
#include<bits/stdc++.h>
#define ll long long
#define MAXN 500005
using namespace std;
struct N{
ll t,c,r;
N(ll t=0,ll c=0,ll r=0):t(t),c(c),r(r){}
};
vector<N>G[MAXN];
ll a[505],dp[505][505],s,t,c,r,ans;
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld%lld",&s,&t,&c,&r);
G[s].push_back(N(t,c,r));
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
dp[j][0]=a[j]-a[i];
int p=i;
for(int k=1;k<=n;k++){
dp[j][k]=a[j]-a[i];
while(p+1<=j&&dp[p+1][k-1]<=a[j]-a[p+1])p++;
dp[j][k]=min(dp[j][k],min(dp[p+1][k-1],a[j]-a[p]));
}
}
for(auto u:G[i])
ans=max(dp[u.t][u.r]*u.c,ans);
}
cout<<ans;
}