The fast-food shop owner rewards employees by providing N types of ingredients for them to make burgers. The owner arranges all the ingredients on the table in a line. Employees must move along the edge of the table from left to right. When passing by ingredients, they can choose not to take or take one serving of ingredients to stack on top of the existing burger.
Xiao Ming hopes to make a burger that he considers the most delicious. The definition of a delicious burger is as follows:
1. For each type of ingredient i, Xiao Ming assigns a deliciousness score Si. The higher the total score of all the ingredients he gets, the better.
2. He cannot allow ingredients with the same attribute to be adjacent when stacking them, as it would severely affect the deliciousness of the food.
For example:
The owner prepares N = 7 types of ingredients arranged in a line from left to right, numbered 0 to 6 sequentially.
Here's the table showing the deliciousness scores and attributes of the ingredients as given by Xiao Ming. If Xiao Ming selects ingredients numbered 0, 1, 4, and 6 sequentially, with non-adjacent ingredients of the same attribute when stacked, he can earn a score of 2 + 7 + 4 + 9 = 22 points.
Ingredient i: 0 1 2 3 4 5 6
Deliciousness Si: 2 7 5 3 4 6 9
Attribute Wi: 1 2 2 1 1 3 3
Please write a program to help Xiaoming calculate the maximum deliciousness of his burger.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line contains two positive integers N and K, indicating there are N types of burger ingredients and these ingredients have a total of K attributes. The second line contains N positive integers S0 to SN-1, separated by a space, representing the deliciousness of these burger ingredients. The third line contains N integers W0 to WN-1, separated by a space, representing the attributes of these burger ingredients. | Please output an integer representing the highest deliciousness that Xiao Ming can obtain according to the above rules. |
| 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 |
Thought Process
When collecting W, you can partition W, adding the maximum value Si from the same partition to the answer.
Default a variable for the current block. If the received block is different from the current block, add the maximum deliciousness of the previous block to the answer, and set the current block to the received number.
Sample Code－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