第 iii 个景点的加油站的费用为,然后就可以用单
分类:旅游

solution

看到 (dis>=10^9) 和 (n<=100卡塔尔这种事物,要想开倍增Floyed,首先要开采大家不可能把油记录在dp状态之中不然开不下,大家着想枚举加油地点.
咱俩定义 (dp[i][j]) 表示从 (i)出发,在j加满油,花费 (j卡塔尔(英语:State of Qatar) 元钱能够走的最大间距,答案就是满足 (dp[i][j]>=d卡塔尔的最大j,所以大家要想艺术预管理出这一个,然后询问就可以长足回答了,(dp[i][j]=Max(dp[k][j-p[i]] dis[j][k])),(dis[i][j]) 表示从 (i卡塔尔(قطر‎ 出发直达 (j卡塔尔,经走道路数不超越 (Min(c[i],C)卡塔尔(قطر‎的最中间隔,能够倍增Floyd预管理出来,然后dp数组具备二分性,能够二分回答复质询问,可是小编爆枚也过了,最坏10^9,常数太小了,哎...

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define RG register
using namespace std;
typedef long long ll;
const int N=105,M=2005;
const ll inf=2e15;
int n,m,C,T,p[N],c[N];ll w[N][N][20];
ll f[N],g[N],dis[N][N],dp[N][N*N];

void work()
{
    scanf("%d%d%d%d",&n,&m,&C,&T);
    for(int i=1;i<=n;i  ){
        scanf("%d%d",&p[i],&c[i]);
        if(c[i]>C)c[i]=C;
    }
    int x,y,z;
    for(int i=1;i<=n;i  )
        for(int j=1;j<=n;j  )
            for(int k=0;k<=18;k  )
                w[i][j][k]=-inf;
    for(int i=1;i<=n;i  )w[i][i][0]=0;
    for(int i=1;i<=m;i  ){
        scanf("%d%d%d",&x,&y,&z);
        w[x][y][0]=Max(w[x][y][0],z);
    }
    for(int k=1;k<=18;k  )
        for(int l=1;l<=n;l  )
            for(int i=1;i<=n;i  )
                for(int j=1;j<=n;j  )
                    w[i][j][k]=Max(w[i][j][k],w[i][l][k-1] w[l][j][k-1]);

    for(int i=1;i<=n;i  ){
        for(int j=1;j<=n;j  )
            g[j]=(i==j?0:-inf),f[j]=-inf;

        for(int k=18;k>=0;k--){
            if(((1<<k)&c[i])==0)continue;
            for(int j=1;j<=n;j  ){
                for(int l=1;l<=n;l  )
                    f[j]=Max(f[j],g[l] w[l][j][k]);
            }
            for(int j=1;j<=n;j  )g[j]=f[j];
        }
        for(int j=1;j<=n;j  )dis[i][j]=g[j];
    }

    int lim=n*n;
    for(int k=0;k<=lim;k  ){
        for(int i=1;i<=n;i  ){
            if(k<p[i])continue;
            for(int j=1;j<=n;j  )
                dp[i][k]=Max(dp[i][k],dp[j][k-p[i]] dis[i][j]);
        }
    }
    while(T--){
        scanf("%d%d%d",&x,&y,&z);
        int ans=y 1;
        for(int i=0;i<=y;i  ){
            if(dp[x][i]>=z){ans=i;break;}
        }
        printf("%dn",y-ans);
    }
}

int main()
{
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    work();
    return 0;
}

图片 1

Description

T 城是叁个漫游城市,具备 nnn 个景点和 mmm 条道路,全部景点编号为 1,2,...,n1,2,...,n1,2,...,n。每条道路连接那 nnn 个景区中的某八个景区,道路是单向交通的。每条道路皆有贰个长短。
为了便于旅游,每一种景点都有壹个加油站。第 iii 个景点的加油站的费用为 pip_ip​i​​,加油量为 cic_ic​i​​。若汽车在第 iii 个景点加油,则供给耗费pip_ip​i​​ 元钱,之后车的油量将被加至油量上限与 cic_ic​i​​ 中的很小值。然则借使加油前小车油量已经相当的大于 cic_ic​i​​,则不能在该景点加油。
小 C 希图赶到 T 城参观。他的小车油量上限为 CCC。旅游起来时,汽车的油量为 000。在游览进度中:
1、当汽车油量大于 000 时,小车能够沿从日前途区出发的人身自由一条道路到达另贰个山清水秀(不能够只走道路的大器晚成局部),小车油量将裁减111;
2、当小车在景点 iii 且当前油量小于 cic_ic​i​​ 时,小车能够在眼下山水加油,加油需开销 pip_ip​i​​ 元钱,那样小车油量将成为 min{ci,C}min{c_i,C}min{c​i​​,C}。
一回旅游的总费用等于每便加油的费用之和,旅游的总路程等于每趟经走廊路的长度之和。注意数次在平等景点加油,开销也要计算多次,同样地,几次经过同一条道路,路程也要计算多次。
小 C 布置骑行 TTT 次,每便旅游前,小 C 都钦定了该次旅游的起源和对象路程。由于路途分化,每一回出发前带的钱也差别。为了存小钱,小 C 供给在参观前先规划好旅游门路(满含观景的门道和加油的方案),使得从源点出发,根据该旅游门路旅游结束后总路程不低于指标路程,且剩下的钱尽大概多。请您设计最优旅游路径,总括那TTT 次旅游每回甘休后最多能够剩下多少钱。

  分明那题能够转化成维护不在车的里面包车型地铁事物的细小值, 援救插入和删去最初现身的值,然后就可以用单调队列了T T

  被从前本身瞎YY的东西坑了T T...单调队列实乃足以保障这种操作的....

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define uint unsigned int
using namespace std;
const int maxn=20000010, inf=1e9;
int n, m, a, b, d, T, l, r, L, R, up, fir, firans;
int p[maxn], h[maxn], q[maxn];
uint ans_sum, cur_ans;    
bool fly[maxn], car[maxn];
namespace IO{
    int c;
    unsigned int seed;
    unsigned int randnum(){
        seed^=seed<<13;
        seed^=seed>>17;
        seed^=seed<<5;
        return seed;
    }

    inline int read(int &x){scanf("%d",&x);return x;}
    inline void init_case(int &m,int &a,int &b,int &d,int p[]){
        scanf("%d%u%d%d%d%d",&m,&seed,&a,&b,&c,&d);
        for(int i=1;i<=m;i  ){
            if(randnum()%c==0) p[i]=-1;
            else p[i]=randnum()%b;
        }
    }

    inline void update_ans(unsigned int &ans_sum,unsigned int cur_ans,int no){
        const static unsigned int mod=998244353;
        ans_sum^=(long long)no*(no 7)%mod*cur_ans%mod;
    }
}
using IO::read;
using IO::init_case;
using IO::update_ans;
inline void qpush(int x)
{
    while(L<=R && q[R]>=x) R--;
    q[  R]=x;
}
inline int min(int a, int b){return a<b?a:b;}
int main()
{
    read(T);
    while(T--)
    {
        init_case(m, a, b, d, p);
        up=max(a 1, b);
        memset(fly, 0, (up 1));
        memset(car, 0, (up 1));
        L=1; R=0; l=1; r=0; ans_sum=0; firans=a 1;
        for(int i=0;i<=a;i  ) car[i]=1;
        for(int i=1;i<=m;i  )
        {
            cur_ans=0;
            if(p[i]==-1) 
            {
                if(l<=r && !d) 
                {
                    if(L<=R && q[L]==h[l]) L  ;
                    fly[h[l  ]]=0, cur_ans=(L<=R)?min(firans, q[L]):firans;
                }
            }
            else
            {
                if(!car[p[i]])
                {
                    car[p[i]]=1;
                    while(car[firans]) firans  ;
                    cur_ans=(L<=R)?min(firans, q[L]):firans;
                }
                else if(car[p[i]] && !fly[p[i]] && !d) fly[p[i]]=1, h[  r]=p[i], qpush(p[i]), cur_ans=(L<=R)?min(firans, q[L]):firans;
                else if(l<=r && !d)
                {
                    if(L<=R && q[L]==h[l]) L  ;
                    fly[h[l  ]]=0, cur_ans=(L<=R)?min(firans, q[L]):firans;
                }
            }    
            update_ans(ans_sum, cur_ans, i);
        }
        printf("%un", ans_sum);
    }
    return 0;
}

View Code

图片 2图片 3

本文由澳门网上网站大全娱乐发布于旅游,转载请注明出处:第 iii 个景点的加油站的费用为,然后就可以用单

上一篇:读欣频《人生创意课》,想要过丰富的人生 下一篇:没有了
猜你喜欢
热门排行
精彩图文