a319. TOI 2021/10 潛力組：美味漢堡

題目描述

桌上的 N 種配料依序排列。你由左往右經過它們，每種可以略過，或取一份加到漢堡頂端。第 i 種配料的美味分數為 S[i]，屬性為 W[i]。選出的配料順序不能改變，且漢堡中相鄰兩份配料的屬性必須不同。請求出可得到的最大美味分數總和。

輸入格式

第一行為 N、K，表示配料數及屬性種類數。 第二行為 N 個分數 S[i]，第三行為 N 個屬性 W[i]。 1 ≤ N ≤ 1000000；1 ≤ K ≤ 1000；1 ≤ S[i] ≤ 1000；1 ≤ W[i] ≤ K。

輸出格式

輸出合法選擇的最高總分。

來源

TOI 2021/10/25~2021/10/29 潛力組〈美味漢堡〉。本題以自寫文字重述規則，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202110/Hamburger.pdf