i751. E.瘋狂購物（shop） - 高中生程式解題系統

內容

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

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

輸入說明

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

$1 \leq N, M \leq 1000$

$- 1 \leq f_{i} < i$

$1 \leq c i, d i \leq 1000$

輸出說明

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

範例輸入 #1

1 1
-1
1 1

範例輸出 #1

範例輸入 #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

範例輸出 #2

測資資訊：

記憶體限制： 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

提示：

範例 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 \leq 15$
subtask 2 30% : 對於所有的 $f_{i}$ 皆滿足 $f_{i} = - 1$
subtask 3 50% : other

標籤:

出處:

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

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」