g544. 美味漢堡 (Hamburger) - 高中生程式解題系統

內容

速食店老闆為了獎勵員工，免費提供 $N$ 種配料給員工們做漢堡。老闆將所有配料排在桌上形成一列，員工必須沿著桌邊由左至右移動，經過配料時可以選擇不拿或拿取一份配料疊在現有漢堡的最上面。
小明希望能做出一份他認為最好吃的漢堡，所謂好吃漢堡的定義如下
(1) 每一種配料 $i$ 小明都會評分出美味程度 $S_{i}$ ，他拿到的所有配料總分越大越好
(2) 不能讓相同屬性的配料在堆疊時相鄰，不然會嚴重影響食物的美味程度。
舉例而言：
老闆準備 $N = 7$ 種配料排成由左至右依序一列編號為 $0$ ~ $6$ 。

小明給予配料的美味程度和屬性如下表所示。小明如果依序選擇編號 $0$ 、 $1$ 、 $4$ 和 $6$ 的配料，相同屬性的配料不會在堆疊時相鄰，而且可得 $2 + 7 + 4 + 9 = 22$ 分。

配料 $i$ 0 1 2 3 4 5 6
美味程度 $S_{i}$ 2 7 5 3 4 6 9
屬性 $W_{i}$ 1 2 2 1 1 3 3

請寫一個程式幫助小明計算他的漢堡的最高美味程度。

輸入說明

第一行有
兩個正整數 $N$ 和 $K$ 代表有 $N$ 種漢堡配料且配料共有 $K$ 種屬性。

第二行有 $N$ 個正整數 $S_{0}$ , $\dots$ , $S_{N - 1}$
兩兩之間以一個空白隔開，表示這些漢堡配料的美味程度。

第三行有 $N$ 個整數 $W_{0}$ , $\dots$ , $W_{N - 1}$ 兩兩之間以一個空白隔開，表示這些漢堡配料的屬性。

$1 \leq N \leq 10^{6}$

$1 \leq K \leq 10^{3}$

$1 \leq S_{i} \leq 10^{3}$

$1 \leq W_{i} \leq K$

輸出說明

請輸出一個整數表示小明依照上述規則能得到的最高美味程度。

範例輸入 #1

7 3
2 7 5 3 4 6 9
1 2 2 1 1 3 3

範例輸出 #1

範例輸入 #2

6 2
1 3 2 1 7 5
1 1 1 2 1 1

範例輸出 #2

範例輸入 #3

5 1
9 3 10 3 10
1 1 1 1 1

範例輸出 #3

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (10%): 1.0s , <10M
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1M
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <10M
不公開測資點#7 (10%): 1.0s , <10M
不公開測資點#8 (10%): 1.0s , <10M
不公開測資點#9 (10%): 1.0s , <10M

提示：

第一組(10分)： $K = 1$
第二組(20分)： $N \leq 20$
第三組(30分)： $N \leq 10^{3}$
第四組(40分)：無特別限制

標籤:

出處:

TOI 練習賽 202110 潛力組 [管理者： fire5386 (becaidorz) ]

編號	身分	題目	主題	人氣	發表日期
40304	toseanlin@gm ... (Dr. SeanXD)	g544	C++詳解－分區取最大值	193	2024-05-08 10:54
27993	liu92112711 ((?))	g544	60%TLE 可能是卡在cin	741	2021-11-08 17:05
27952	r1cky (hehe)	g544	Java 解題心得	773	2021-11-06 21:31