Пожалуйста помогите с задачей

Сама задача:

Задача

Тесты:

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 из четырёх столбцов - на лошади мечом, на лошади кольцом, пешкодралом мечом, аналогично кольцом.

Для каждого противника делаете возможные переходы из верхней строчки в нижнюю, выбирая наиболее выгодный вариант.

Заполнив таблицу, в последней строчке будете иметь минимальные затраты.

Однако, динамическое программирование получается. И таблица, собственно не нужна- достаточно двух текущих строчек.

→ Ссылка