Пожалуйста помогите с задачей
Сама задача:
Тесты:
5 2 1
10101
15 3 20
111101111111111
5 1 1
11111
20 3 20
11110001011111111111
Мой код:
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
// 1 меч
// лошадь w слезть/залезть
// кольцо s
// n кол-во воинов
// 1 - дракон 0 - орк
int n, s, w, total_energy = 0;
bool horse_status = false;
string monsters;
cin >> n >> s >> w;
cin >> monsters;
cout << endl;
for (int i = 0; i < n; i++) {
if (monsters[i] == '1') {
// дракон
if (horse_status == true && 1 < s) {
total_energy += 1;
}
else if (horse_status == false && (w + 1) < s) {
horse_status = true;
total_energy += w + 1;
}
else {
total_energy += s;
}
}
else {
// орк
if (horse_status == false && 1 < s) {
total_energy += 1;
}
else if (horse_status == true && (w + 1) < s) {
horse_status = false;
total_energy += w + 1;
}
else {
total_energy += s;
}
}
}
cout << total_energy << endl;
}
Получаю в 50 процентах верные ответы и в 50 неверные, но почти близкие к истине.
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Почему бы не сделать табличку длиной n из четырёх столбцов - на лошади мечом, на лошади кольцом, пешкодралом мечом, аналогично кольцом.
Для каждого противника делаете возможные переходы из верхней строчки в нижнюю, выбирая наиболее выгодный вариант.
Заполнив таблицу, в последней строчке будете иметь минимальные затраты.
Однако, динамическое программирование получается. И таблица, собственно не нужна- достаточно двух текущих строчек.
