i751. E.瘋狂購物(shop)
Tags :
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-08 10:02

Content

三口羊現在經營著一間商店,裡面有 $N$ 樣商品,在這間商店中有著許多不同的優惠,他想知道在客人有 $M$ 元時且購買到的商品不重複時最多可以獲得價值為多少的商品。

具體而言,商品優惠如下:
這些商品彼此之間會形成一顆有向森林(沒有環),對於第 $i$ 個商品,消費者可以花費 $c_i$ 元將第 $i$ 樣商品買下來,同時 $c_i$ 也代表了第 $i$ 樣物品的價值,也可以花費 $d_i$ 元將以第 $i$ 樣物品為root的子樹下的商品通通買走。

Input

第一行有兩個整數$N,M$ 代表意義如題序所敘述
第二行有 $N$ 個整數 $f_i (0 \le i < N)$ 第 $i$ 樣物品的父節點(若為 -1 代表該樣物品沒有父節點)
接下來有 $N$ 行,每行有 $2$ 個整數 $c_i$,$d_i$ 代表意義如題序所敘述

$1\le N,M\le 1000$

$-1 \le f_i < i$

$1\le ci,di \le 1000$

Output

請輸出一個整數,代表顧客在有 $M$ 塊錢時可以購買最大的商品總價值是多少

Sample Input #1
1 1
-1
1 1

Sample Output #1
1
Sample Input #2
10 10
-1 0 0 0 1 3 -1 -1 6 4
6 7
3 8
2 3
5 105
3 9
2 3
2 7
1 8
77 3
2 9
Sample Output #2
100
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <1M
公開 測資點#17 (5%): 1.0s , <1M
公開 測資點#18 (5%): 1.0s , <1M
公開 測資點#19 (5%): 1.0s , <1M
Hint :

範例 2 說明
畫完樹狀圖後,可發現:
把以 0 為樹根的子樹買下來,
(以 7 塊錢買下總價值 23 的物品,被買下來的物品編號分別為 0、1、2、3、4、5、9)
再把以 8 為樹根的子樹買下來,
(以 3 塊錢買下總價值 77 的物品,被買下來的物品編號只有 8,因為 8 沒有子節點)
(註:只要錢足夠,用 77 元買下 8 號物品也可以的,但明顯地不符合求最佳解的策略)
以此方法購物,可以用 7+3=10 元買到總價值 23+77=100 的物品,
並且你會發現沒有其他買法可以買到更高總價值的物品。

subtask 1 20% : $N\le 15$
subtask 2 30% : 對於所有的$f_i$皆滿足$f_i=-1$
subtask 3 50% : other

Tags:
出處:
2022成功高中校內賽 [管理者: CGSH (快加油吧~~) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」