g544: 美味漢堡 (Hamburger)
Tags :
Accepted rate : 75人/87人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-11-23 18:38

Content

速食店老闆為了獎勵員工,免費提供 $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

 

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

Input

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

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

第三行有 $N$ 個整數 $W_0$ , $\dots$ , $W_N$ 兩兩之間以一個空白隔開,表示這些漢堡配料的屬性。

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

Output

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

Sample Input #1
7 3
2 7 5 3 4 6 9
1 2 2 1 1 3 3
Sample Output #1
22
Sample Input #2
6 2
1 3 2 1 7 5
1 1 1 2 1 1
Sample Output #2
11
Sample Input #3
5 1
9 3 10 3 10
1 1 1 1 1
Sample Output #3
10
測資資訊:
記憶體限制: 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
Hint :

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

Tags:
出處:
TOI練習賽202110潛力組 [管理者:
fire5386 (fffelix)
]


ID User Problem Subject Hit Post Date
27993
liu92112711 ((?))
g544
64 2021-11-08 17:05
27952
r1cky (木叢欉木叢)
g544
Java 解題心得
52 2021-11-06 21:31