P2583 地铁间谍

    • 337通过
    • 1K提交
  • 题目提供者 Timothy
  • 评测方式 云端评测
  • 标签 前缀和 动态规划,动规,dp 枚举,暴力
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    特工玛利亚被送到S市执行一个特别危险的任务。她需要利用地铁完成他的任务,S市的地铁只有一条线路运行,所以并不复杂。

    玛利亚有一个任务,现在的时间为0,她要从第一个站出发,并在最后一站的间谍碰头。玛利亚知道有一个强大的组织正在追踪她,她知道如果一直呆在一个车站,她会有很大的被抓的风险,躲在运行的列车中是比较安全的。所以,她决定尽可能地呆在运行的列车中,她只能往前或往后坐车。

    玛利亚为了能准时且安全的到达最后一个车站与对方碰头,需要知道在在车站最小等待时间总和的计划。你必须写一个程序,得到玛丽亚最短的等待时间。当然,到了终点站之后如果时间还没有到规定的时刻,她可以在车站里等着对方,只不过这个等待的时刻也是要算进去的。

    这个城市有n个车站,编号是1-n,火车是这么移动的:从第一个车站开到最后一个车站。或者从最后一站发车然后开会来。火车在每特定两站之间行驶的时间是固定的,我们也可以忽略停车的时间,玛利亚的速度极快,所以他可以迅速上下车即使两辆车同时到站。

    输入输出格式

    输入格式:

    输入文件包含多组数据,每组数据都由7行组成

    第1行:一个正整数N(2<=N<=50)表示站的数量

    第2行:一个正整数T(0<=T<=2000)表示需要的碰头时间

    第3行:1-(n-1)个正整数(0<ti<70)表示两站之间列车的通过时间

    第4行:一个整数M1(1<=M1<=50)表示离开第一个车站的火车的数量

    第5行:M1个正整数:d1,d2……dn,(0<=d<=250且di<di+1)表示每一列火车离开第一站的时间

    第6行:一个正整数M2(1<=M2<=50)表示离开第N站的火车的数量

    第7行:M2个正整数:e1,e2……eM2,(0<=e<=250且ei<ei+1)表示每一列火车离开第N站的时间

    最后一行有一个整数0。

    输出格式:

    对于每个测试案例,打印一行“Case Number N: ”(N从1开始)和一个整数表示总等待的最短时间或者一个单词“impossible”如果玛丽亚不可能做到。按照样例的输出格式。

    输入输出样例

    输入样例#1: 复制
    4
    55
    5 10 15
    4
    0 5 10 20
    4
    0 5 10 15
    4
    18
    1 2 3
    5
    0 3 6 10 12
    6
    0 3 5 7 12 15
    2
    30
    20
    1
    20
    7
    1 3 5 7 11 13 17
    0
    
    输出样例#1: 复制
    Case Number 1: 5
    Case Number 2: 0
    Case Number 3: impossible
    

    说明

    第一组样例说明,她0分钟时上车,在3号站下车,立刻坐上(0分始发)15分开的车回去,到2号车站,立刻坐上(20分始发)25开的车到终点,50分到,还需要等待5分钟。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。