P3786 萃香抱西瓜

    • 59通过
    • 240提交
  • 题目提供者 orangebird
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 最短路 状态压缩,状压 进制 洛谷原创
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    伊吹萃香(Ibuki Suika)正在魔法之森漫步,突然,许多西瓜(Suika)从四周飞来,划出了绚丽的轨迹。虽然阵势有点恐怖,但她还是决定抱走一些西瓜。

    题目描述

    萃香所处的环境被简化为一个长为h,宽为w的网格平面。X坐标范围为[1,w],y坐标范围为[1,h]。

    她初始(第1个时刻)站在坐标为sx,sy的方格。

    西瓜可能在任意一个方格出现,在每个时间单位,它们可能向任何一个方向移动,也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为n个,但只有m个西瓜可以被萃香抱走,因为其他都太大了,可能会砸伤她。

    整个过程会持续T个时刻。萃香希望可以抱走全部的m个西瓜,并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻,与该西瓜处于同一位置。另外,由于萃香不愿耗费过多体力到处乱跑,她每个时刻可以选择静止不动,也可以选择移动到相邻的四个格子之一,只要不越出环境边界。如果选择移动到相邻格子,则算作移动了一次。(第1个时刻萃香刚站定,无法移动)

    在每个时刻,如果萃香选择移动,可以认为萃香与西瓜同时从原来的位置移到了新的位置,没有先后顺序。

    萃香想要知道,不被任何一个大西瓜砸中,并得到所有的m个小西瓜的情况下,最少需要移动多少次。

    输入输出格式

    输入格式:

    第一行五个整数h,w,T,sx,sy,含义见题目描述。

    第二行两个整数n,m,含义见题目描述。

    接下来n段数据,每一段描述了一个西瓜的出现位置,时间,移动方式,是否可以被抱走等内容,具体如下:

    首先一行,两个整数t1,t2,表示西瓜在t1时刻出现, t2时刻消失。若t2=T+1,表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。

    接下来一行一个整数a,只能为0或1,0表示这个西瓜需要避开,1表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有m个。

    接下来t2-t1行,每一行两个整数x,y,顺序描述了从t1时刻到t2-1时刻,该西瓜的坐标。西瓜的移动不一定是连续的,并且是一瞬间完成的,所以无需考虑萃香是否站在了移动路径上。

    输出格式:

    如果萃香在整个T时刻内无法避免被大西瓜砸中或者无法收集到所有m个小西瓜,输出-1,否则输出一个整数,表示萃香需要移动的最少次数。

    输入输出样例

    输入样例#1: 复制
    5 5 10 3 3
    1 1
    1 11
    1
    3 4
    5 2
    3 5
    1 1
    5 4
    3 4
    2 1
    1 1
    1 1
    5 5
    输出样例#1: 复制
    1

    说明

    样例说明:第2~4个时刻萃香站着不动,在第6个时刻,西瓜出现在萃香旁边,萃香移动到(3,4)位置即可抱走这个西瓜。

    数据范围和提示:

    子任务可能出现两种特殊性质A和B

    A: 所有西瓜t1=1,t2=T+1

    所有西瓜全程都静止在原地,不会发生移动。

    B:m=0

    共有10个子任务。

    对于子任务1,具有特殊性质A和B

    对于子任务2~3,仅具有特殊性质A

    对于子任务4~5,仅具有特殊性质B

    对于子任务6~10,不具有任何一个特殊性质。

    对于全部子任务

    1<=所有横坐标范围<=w

    1<=所有纵坐标范围<=h

    1<=h,w<=5
    1<=T<=100
    1<=t1<=T
    2<=t2<=T+1
    t1<t2
    1<=n<=20
    0<=m<=10
    m<=n

    一个位置不会同时出现两个或以上西瓜。

    命题人:orangebird

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