P3360 偷天换日

    • 344通过
    • 733提交
  • 题目提供者 永忻
  • 评测方式 云端评测
  • 标签 树形动规
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    神偷对艺术馆内的名画垂涎欲滴准备大捞一把。

    题目描述

    艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅,就

    是分为两个走廊。每个展览厅内都有若干幅画,每副画都有一个价值。经过走廊和偷画都是

    要耗费时间的。

    警察会在n 秒后到达进口,在不被逮捕的情况下你最多能得到的价值。

    输入输出格式

    输入格式:

    第一行一个整数 n(n≤600)。

    第二行若干组整数,对于每组整数(t,x),t 表示进入这个展览厅或经过走廊要耗费 t

    秒的时间,若x>0 表示走廊通向的展览厅内有x 幅画,接下来

    x对整数(w,c)表示偷一幅价值为 w 的画需要 c秒的时间。若

    x=0 表示走廊一分为二。(t,c≤5; x≤30)

    输入是按深度优先给出的。房间和走廊数不超过 300 个。

    输出格式:

    仅一个整数,表示能获得的最大价值。

    输入输出样例

    输入样例#1: 复制
    50 
    5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4 
    输出样例#1: 复制
    1500

    说明

    来源:改编

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