速食店老闆為了獎勵員工，免費提供 N 種配料給員工們做漢堡。老闆將所有配料排在桌上形成一列，員工必須沿著桌邊由左至右移動，經過配料時可以選擇不拿或拿取一份配料疊在現有漢堡的最上面。
小明希望能做出一份他認為最好吃的漢堡， 所謂好吃漢堡的定義如下
(1) 每一種配料 i 小明 都會評分出美味程度 Si，他拿到的所有配料總分越大越好
(2) 不能讓相同屬性的配料在堆疊時相鄰，不然會嚴重影響食物的美味程度。
舉例而言：
老闆準備 N = 7 種配料排成由左至右依序一列編號為 0 ~ 6。
小明給予配料的美味程度和屬性如下表所示。小明如果依序選擇編號 0、1、4 和 6 的配料 ，相同屬性的配料不會在堆疊時相鄰，而且可得 2 + 7 + 4 + 9 = 22 分。
配料 i：0 1 2 3 4 5 6
美味程度 Si：2 7 5 3 4 6 9
屬性 Wi：1 2 2 1 1 3 3
請寫一個程式幫助小明計算他的漢堡的最高美味程度。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有兩個正整數 N 和 K，代表有 N 種漢堡配料且配料共有 K 種屬性。 第二行有 N 個正整數 S0～SN-1。 兩兩之間以一個空白隔開， 表示這些漢堡配料的美味程度。 第三行有 N 個整數 W0～WN-1。 兩兩之間以一個空白隔開，表示這些漢堡配料的屬性。 | 請輸出一個整數表示小明依照上述規則能得到的最高美味程度。 |
| 7 3 2 7 5 3 4 6 9 1 2 2 1 1 3 3 | 22 |
| 6 2 1 3 2 1 7 5 1 1 1 2 1 1 | 11 |
| 5 1 9 3 10 3 10 1 1 1 1 1 | 10 |
解題思路
在收 W 的時候可以將 W 分區，將同一個分區的最大值 Si 加到答案裡。
預設一個目前區塊的變數，如果收到的區塊和目前區塊不一樣，則將上一個區塊的最大美味度加到答案中，並且將目前區塊設定為收到的數字。
範例程式碼－ZeroJudge G544: 美味漢堡 (Hamburger)
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N, K;
cin >> N >> K;
vector<int>S, W;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
S.push_back(tmp);
}
int max = -999, current, ans = 0;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
W.push_back(tmp);
if (i == 0)
{
max = S[i];
current = tmp;
continue;
}
if (tmp == current)
{
if (S[i] > max) max = S[i];
if (i == N-1) ans += max;
continue;
}
current = tmp;
ans += max;
max = S[i];
if (i == N-1) ans += max;
}
cout << ans << "\n";
}
//ZeroJudge G544
//Dr. SeanXD