| 题目名称 | 1028. [NOIP 2011冲刺九]引爆炸弹 |
|---|---|
| 输入输出 | bombb.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 王者自由
于2012-08-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：41， 提交：104， 通过率：39.42% | ||||
 Shirry |
100 | 0.285 s | 2.66 MiB | C++ |
 Lethur |
100 | 0.334 s | 3.55 MiB | C++ |
 zxj |
100 | 0.339 s | 6.42 MiB | C++ |
 TARDIS |
100 | 0.374 s | 7.94 MiB | C++ |
 soler |
100 | 0.413 s | 7.19 MiB | C++ |
 Makazeu |
100 | 0.439 s | 4.12 MiB | C++ |
 feng |
100 | 0.456 s | 43.01 MiB | C++ |
 Rapiz |
100 | 0.463 s | 2.99 MiB | C++ |
 confoo |
100 | 0.470 s | 2.91 MiB | C++ |
 KZNS |
100 | 0.471 s | 4.88 MiB | C++ |
| 本题关联比赛 | |||
| 20121012上午 | |||
| 关于 引爆炸弹 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
树形dp+背包
Shirry
2017-04-19 18:41
7楼
| ||||
|
自己挣扎了一下午最多60。。。写的又长又慢
  Hzoi_Queuer
2016-11-08 20:18
6楼
| ||||
|
回复 @Truth.Cirno :
根据题意不存在环…… Rapiz
2016-10-28 11:17
5楼
| ||||
|
我只是想刷刷水题来着……
| ||||
|
为毛在邮箱里存的代码拿出来会形变。
| ||||
|
让我感到欣慰的是，为何本题没有环？
希望管理员添加说明，或者添加数据 5 1 2 1 3 1 4 1 5 1 1 1 | ||||
|
记得开long long
| ||||
浮生随想
Ezio
Truth.Cirno引爆炸弹
问题描述：
有n个炸弹，有些炸弹牵了一根单向引线（也就是说引线只有在这一端能被炸弹点燃），只要引爆了这个炸弹，用引线连接的下一个炸弹也会爆炸。每个炸弹还有个得分，当这个炸弹被引爆后就能得到相应得分。
现在要你引爆k个炸弹，使得分最大。
输入说明：
第1行两个整数n、k。
接下来n行每行两个整数a[i]、b[i]。a[i]表示这个炸弹用引线连接的下一个炸弹，如果a[i]为0，则表示这个炸弹没连接引线。b[i]表示这个炸弹的得分。
输出说明：
仅一个数，表示最大得分。
样例输入输出：
|
bombb.in |
|
8 2 0 1 1 1 2 100 2 100 0 1 5 1 6 2 6 2 |
|
bombb.out |
|
202 |
数据范围：
1≤b[i]≤1000000
对于30%的数据，n≤1000 k≤30
对于60%的数据，n≤50000 k≤100
对于100%的数据，n≤200000 k≤500