Mayflyyh
Mayflyyh
MayFlyyh's Blog
LOJ #539「LibreOJ NOIP Round #1」旅游路线

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);
    }
}
本文链接:http://www.mayflyyh.com/archives/316
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      LOJ #539「LibreOJ NOIP Round #1」旅游路线
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

LOJ #539「LibreOJ NOIP Round #1」旅游路线
T 城是一个旅游城市,具有n个景点和m条道路,所有景点编号为 1,2,...,n。每条道路连接这n个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。 为了方便旅游,每个景点…
扫描二维码继续阅读
2018-08-16