test 190720 libreoj539 「LibreOJ NOIP Round #1」旅游路线

缺乏、安全感 2021-11-01 23:28 108阅读 0赞

[https://loj.ac/problem/539][https_loj.ac_problem_539]

填坑......

首先想$f\_\{i,j,k\}$表示在$i$点，剩余$j$元与$k$个单位的油，可以行驶的最远距离

但其实我们发现，$f\_\{i,j,k\}$要么从$f\_\{s,j,k+1\}$转移过来，要么从$f\_\{i,k-p\_i,min(c\_i,C)\}$转移过来，那么最后一维就显得有点多余l了

于是考虑$f\_\{i,j\}$表示在$i$点，剩余$j$元并且下次加油就在$i$点加，能行走的最远距离，枚举下次加油的节点转移即可

要预处理处$mx\_\{i,j\}$表示从$i$走到$j$，经过不超过$c\_i$条边，可以产生的最大贡献

用一个类似floyd+倍增优化的方法

#pragma GCC optmize(2)
    #include<bits/stdc++.h>
    using namespace std;
    const int N=105,inf=1e9;
    int n,m,C;
    int p[N],c[N];
    int f[N][N*N],g[N][N][20],mx[N][N],t[N][N];
    void cmax(int x,int &y) {x>y?y=x:1;}
    int rd()
    {
        char ch='!'; int res=0;
        while(ch<'0' || ch>'9') ch=getchar();
        while(ch>='0' && ch<='9') res=res*10+ch-'0',ch=getchar();
        return res;
    }
    int main()
    {
        freopen("trip.in","r",stdin); freopen("trip.out","w",stdout);
        int T;
        n=rd(),m=rd(),C=rd(),T=rd();
        for(int i=1;i<=n;++i)
        {
            p[i]=rd(),c[i]=rd();
            c[i]>C?c[i]=C:1;
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                mx[i][j]=t[i][j]=-inf;
                for(int k=0;k<=16;++k) g[i][j][k]=i==j?0:-inf;    
            }
        for(int i=1;i<=m;++i)
        {
            int u,v,w;
            u=rd(),v=rd(),w=rd();
            cmax(w,g[u][v][0]);
        }
        for(int i=1;i<=16;++i)
            for(int j=1;j<=n;++j)
                for(int k=1;k<=n;++k)
                    for(int l=1;l<=n;++l)
                        cmax(g[j][l][i-1]+g[l][k][i-1],g[j][k][i]);
        for(int i=1;i<=n;++i)
        {
            mx[i][i]=0;
            for(int cnt=16;cnt>=0;--cnt)
            if(c[i]>>cnt&1)
            {
                for(int j=1;j<=n;++j)
                    for(int k=1;k<=n;++k)
                        cmax(mx[i][k]+g[k][j][cnt],t[i][j]);
                for(int j=1;j<=n;++j) mx[i][j]=t[i][j];
            }
        }
        for(int j=0;j<=n*n;++j)
            for(int i=1;i<=n;++i)
            {
                if(j<p[i]) continue;
                for(int k=1;k<=n;++k)
                    cmax(f[k][j-p[i]]+mx[i][k],f[i][j]);
            }
        while(T--)
        {
            int s,q,d;
            //scanf("%d%d%d",&s,&q,&d);
            s=rd(),q=rd(),d=rd();
            int ans=lower_bound(f[s]+1,f[s]+q+1,d)-f[s];
            if(f[s][q]<d) puts("-1");
            else printf("%d\n",q-ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/w19567/p/11319736.html

[https_loj.ac_problem_539]: https://loj.ac/problem/539