T 城是一个旅游城市,具有n个景点和m条道路,所有景点编号为 1,2,…,n。每条道路连接这n个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。
为了方便旅游,每个景点都有一个加油站。第i个景点的加油站的费用为 pi,加油量为ci。若汽车在第i个景点加油,则需要花费pi元钱,之后车的油量将被加至油量上限与ci中的较小值。不过如果加油前汽车油量已经不小于 ci,则不能在该景点加油。
小 C 准备来到 T 城旅游。他的汽车油量上限为 C。旅游开始时,汽车的油量为0。在旅游过程中:
1、当汽车油量大于0 时,汽车可以沿从当前景区出发的任意一条道路到达另一个景点(不能只走道路的一部分),汽车油量将减少1;
2、当汽车在景点i且当前油量小于ci时,汽车可以在当前景点加油,加油需花费pi元钱,这样汽车油量将变为 min{ci,C}。
一次旅游的总花费等于每次加油的花费之和,旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油,费用也要计算多次,同样地,多次经过同一条道路,路程也要计算多次。
小 C 计划旅游 T 次,每次旅游前,小 C 都指定了该次旅游的起点和目标路程。由于行程不同,每次出发前带的钱也不同。为了省钱,小 C 需要在旅游前先规划好旅游路线(包括旅游的路径和加油的方案),使得从起点出发,按照该旅游路线旅游结束后总路程不小于目标路程,且剩下的钱尽可能多。请你规划最优旅游路线,计算这 T 次旅游每次结束后最多可以剩下多少钱。
最后T行,每行包含三个正整数 si,qi,di,描述一次旅游计划,旅游的起点为编号为si的景点,出发时带了 qi元钱,目标路程为di
> 2<=n<=100 , 1<=m<=1000 , 1<=C,T<=1e5,pi,ci<=1e5,qi
根据T的规模,可知应该是预处理一下然后O(1)或者O(logn)回答询问,O(1)就是直接回答或者ST表,O(logn)就是线段树、倍增之类。
我们很不容易想到,用G[i][j]表示以i为起点带j元钱能行驶的最远路程记下,然后每次在G[i]中二分一个大于Di的且j最小的答案的答案
状态转移方程:G[i][j]=max{G[i][j-p[i]]+F[i][k]};
其中F[i][j]表示的是从i到j,加一次油能够行驶最远的路程
设 P[i][j][k]=max{F[e]][j][k-1]+l(e))};
其中P[i][j][k] 表示的是从i到j,经过k条边能够行驶最远的路程
其中e是i指向的城市,l(e)是这条边的路程
考虑优化,P[i][j][k]表示从i到j,经过2^j^条边能够行驶的最远距离
P[i][j][s]=max{P[i][k][s-1],P[k][j][s-1]}
然后将C[i]分解为每个2进制,后相加即可
CODE:
#include<bits/stdc++.h>
const int N = 105;
const int inf = 0x3f3f3f3f;
int n,m,C,T,A[N],B[N];
int G[N][N][21],p[N],c[N];
int DP[N][N*N],D[N][N];
inline int read(){
int x=0,flag=1;char c=getchar();
while(!isdigit(c)){if(c=='-')flag=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*flag;
}
int main(){
n=read(),m=read(),C=read(),T=read();
for(int i=1;i<=n;++i){
p[i]=read(),c[i]=read();
c[i]=std::min(c[i],C);
for(int j=1;j<=n;++j){
G[i][j][0]=i==j?0:-inf;
}
}
for(int i=1;i<=m;++i){
int a=read(),b=read(),c=read();
G[a][b][0]=std::max(G[a][b][0],c);
}
for(int k=1;k<=20;++k){
for(int a=1;a<=n;++a){
for(int b=1;b<=n;++b){
G[a][b][k]=-inf;
for(int s=1;s<=n;++s){
G[a][b][k]=std::max(G[a][b][k],G[a][s][k-1]+G[s][b][k-1]);
}
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
A[j]=i==j?0:-inf;
for(int k=20;k+1;k--){
if((c[i]>>k)&1){
for(int j=1;j<=n;++j){
B[j]=-inf;
for(int d=1;d<=n;++d)
B[j]=std::max(B[j],A[d]+G[d][j][k]);
}
for(int j=1;j<=n;++j){
A[j]=B[j];
}
}
}
for(int j=1;j<=n;++j){
D[i][j]=A[j];
}
}
for(int i=0;i<=n*n;++i){
for(int j=1;j<=n;++j){
if(i>=p[j])
for(int k=1;k<=n;++k)
DP[j][i]=std::max(DP[j][i],DP[k][i-p[j]]+D[j][k]);
}
}
while(T--){
int s=read(),q=read(),d=read();
int l=0,r=q+1;
int ans=q+1;
while(l+1<r){
int mid=l+r>>1;
if(DP[s][mid]>=d){
ans=mid;
r=mid;
}
else l=mid;
}
printf("%d\n",q-ans);
}
}
0 条评论