從前有個神奇的地方，他有$\color{#333333}{N}$個格子，編號是$\color{#333333}{1\sim N}$，有一些格子上有金幣可以拿。
而神奇的點在於，每個格子都有一個傳送門可以連接到另外的某個格子，然後再繼續傳送下去，但所有傳送門皆只能觸發一次
值得注意的是，傳送門是格子之間相通的唯一方法，也就是你不能跑到旁邊的格子
某天，你被傳送到這個地方的其中一格，你將從這一格開始，遇到所經過的每一格可以選擇撿起所有金幣或不撿，如果撿起金幣的話會消耗體力值、然後通過該格的傳送門前往下一格。你希望撿走的金幣愈多愈好，因此你一定會一直傳送下去直到無法傳送為止，那麼請問你最多可以撿到幾個金幣呢？
單筆測資
第一行輸入$\color{#333333}{N}$ $\color{#333333}{C}$代表有$\color{#333333}{N}$個格子和$\color{#333333}{C}$的體力值
第二行有$\color{#333333}{N}$個數字$\color{#333333}{X_1\sim X_N}$，第$\color{#333333}{i}$個數字代表第$\color{#333333}{i}$格可以傳送到第$\color{#333333}{X_i}$格
第三行有$\color{#333333}{N}$個數字$\color{#333333}{M_1\sim M_N}$，分別代表每一格的金幣數
第四行有$\color{#333333}{N}$個數字$\color{#333333}{K_1\sim K_N}$，分別代表每一格的消耗體力
第五行有一數$\color{#333333}{S}$代表你從第$\color{#333333}{S}$格開始
輸出最多可以撿到幾個金幣
6 100 2 3 4 5 6 1 10 25 65 25 25 15 8 25 75 29 17 20 1
100
$1 \leq N,C \leq 10^6$
$1 \leq X \leq N$
$1 \leq M \leq 10^6$
$1 \leq K \leq C$
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||