HDU - 4571 Travel in time (不错的dp)

墨蓝 2022-05-23 02:13 101阅读 0赞

[点击打开链接][Link 1]

思路：先用floyd跑出任意两点的最短路，然后用dp\[i\]\[k\]=max(dp\[i\]\[k\], dp\[j\]\[k+cost\]\])转移。dp\[i\]\[k\]代表从原点到达i点在剩余时间为k的情况下，得到的最大S值。

可以想象一下，假如答案是参观其中的n个点。那么答案的S值肯定是这n个点的s值总和，花费就是这n个点的花费加上路径上相邻两个点的最短路。所以dp更确切的含义是从原点到i点，剩余时间为k，i点必须游览的最大值。

于是要想利用转移方程，必须要知道比他S值小的点的dp值，所以对每个点的S值进行排序，

但这样就会产生一个问题，对于原点，排序之后不一定会在第一个位置，可是如果原点不游览的话是可以转移到他前面的点的。所以要虚拟一个超级原点。其S值为-1，花费为0。其次还要虚拟一个超级终点，因为我们转移状态是必须要游览，可以终点可能不被游览，所以超级终点要放在最后，其S值要大于所有值，我设置的为105，花费为0

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    const int INF=0x3f3f3f3f;
    typedef long long ll;
    
    int N, M, T, S, E;
    int dist[110][110];
    int dp[110][310];
    struct node{
        int v, c, id;
    }pos[110];
    
    
    void init(){
        memset(dp, -1,  sizeof(dp));
       for(int i=0; i<=N+1; i++)
        for(int j=0; j<=N+1; j++)
            if(i==j) dist[i][j]=0;
            else dist[i][j]=INF;
    }
    bool cmp(node a, node b){
        return a.v<b.v;
    }
    
    int main(){
        int cas=0, CAS;
        scanf("%d", &CAS);
        while(CAS--){
    
            scanf("%d%d%d%d%d", &N, &M, &T, &S, &E);
            init();
            for(int i=1; i<=N; i++)
            {
                scanf("%d", &pos[i].c); pos[i].id=i-1;
            }
    
            for(int i=1; i<=N; i++){
                scanf("%d", &pos[i].v);
            }
            pos[N+1]=(node){105, 0, N};//超级终点
            pos[N+2]=(node){-1, 0, N+1};//超级原点
            int u, v, w;
            for(int i=1; i<=M; i++)
            {
                scanf("%d%d%d", &u, &v, &w);
                if(w<dist[u][v])
                    dist[u][v]=dist[v][u]=w;
            }
    
            for(int k=0; k<N; k++)
                for(int i=0; i<N; i++)
                    for(int j=0; j<N; j++)
                        dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j]);
    
            for(int i=0; i<N; i++)//对超级原点，超级终点dist初始化
            {
                dist[i][N]=dist[N][i]=dist[E][i];
                dist[i][N+1]=dist[N+1][i]=dist[S][i];
            }
            dist[N+1][N]=dist[N][N+1]=dist[S][E];
    
            sort(pos+1, pos+1+N+2, cmp);
            dp[N+1][T]=0;
            for(int i=1; i<=N+2; i++){
                for(int k=0; k<=T; k++){
                    for(int j=1; j<i; j++){
                        int u=pos[j].id, v=pos[i].id, cost=dist[u][v]+pos[i].c;
                        if(dist[u][v]!=INF && k+cost<=T && pos[i].v>pos[j].v && dp[u][k+cost]!=-1){
                            dp[v][k]=max(dp[v][k], dp[u][k+cost]+pos[i].v);
                        }
                    }
                }
            }
    
            printf("Case #%d:\n", ++cas);
            int ans=105;
            for(int i=0; i<=T; i++)
                ans=max(ans, dp[N][i]);
    
            printf("%d\n", ans-105);//最后要减去超级终点的s值
        }
    
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=4571