ZeroJudge G544: 美味漢堡 (Hamburger)

速食店老闆為了獎勵員工,免費提供 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
ZeroJudge G544 範例測資

解題思路

在收 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

發佈留言