| 题目名称 | 1742. 神偷小智 |
|---|---|
| 输入输出 | steal.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 乌龙猹
于2014-10-17加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：47， 提交：126， 通过率：37.3% | ||||
 HZOI_蒟蒻一只 |
100 | 0.094 s | 0.51 MiB | C++ |
 0_0 |
100 | 0.113 s | 2.61 MiB | C++ |
 YZQ |
100 | 0.121 s | 0.91 MiB | C++ |
 乌龙猹 |
100 | 0.128 s | 0.98 MiB | C++ |
 ☪Repentance soul |
100 | 0.129 s | 0.98 MiB | C++ |
|
乌龙猹 |
100 | 0.129 s | 1.00 MiB | C++ |
 神利·代目 |
100 | 0.129 s | 1.25 MiB | C++ |
 hzoi55223 |
100 | 0.130 s | 1.00 MiB | C++ |
 zhu8655 |
100 | 0.130 s | 1.04 MiB | C++ |
 苜 |
100 | 0.130 s | 23.36 MiB | C++ |
| 关于 神偷小智 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
老子才tm是少打负一！！！！！！
 Hzoi_Ivan
2017-04-17 15:58
8楼
| ||||
|
少打一个-1，
身败名裂  WildRage
2017-04-06 14:37
7楼
| ||||
|
背包挂树上。
 Hallmeow
2017-04-06 14:32
6楼
| ||||
|
不知不觉400题了呢～～O(∩_∩)O
 浮生随想
2016-11-03 21:01
5楼
| ||||
|
@2218 = =
 ztx
2014-10-19 14:00
4楼
| ||||
|
回复 @狂拽炫酷D炸天 :
那你为什么不用C++？鬼才信你会翻译Pascal 乌龙猹
2014-10-18 07:26
3楼
| ||||
|
乌龙猹
2014-10-18 07:06
2楼
| ||||
|
树形DP+背包思想
| ||||
【题目描述】
神偷小智对艺术馆内的名画垂涎欲滴准备大捞一把。艺术馆由若干个展览厅和若干条走廊组成。每一条走廊的尽头不是通向一个展览厅，就是分为两个走廊。每个展览厅内都有若干幅画，每幅画都有一个价值。经过走廊和偷画都是要耗费时间的。警察会在第n秒到达进口，在不被逮捕的情况下小智最多能得到的价值。
【输入格式】
第一行一个整数 n
第二行若干组整数，对于每组整数（t,x），t表示进入这个展览厅或经过走廊要耗费t秒的时间，若x>0表示走廊通向的展览厅内有x幅画,接下来x对整数(w,c)表示偷一幅价值为w的画需要c秒的时间。若x=0表示走廊一分为二。
输入是按深度优先给出的。
【输出格式】
仅一个整数，表示能获得的最大价值。
【样例输入】
50
5 0 10 1 10 1 5 0 10 2 500 1 1000 2 18 1 1000000 4
【样例输出】
1500
【提示】
n≤600；t，c≤5；x≤30
房间和走廊数不超过300个。
注意题目要求你在不被逮捕的情况下得到最多的价值
样例的输入对应于下图
【来源】
hzoi 2014 寒川