Выгодно ли нам вообще нанимать бандитов? Ведь если я правильно понял задачу, заплатив 2*x мы получаем возможность в лучшем случае преодолеть еще x последующих бандитов бесплатно, что в лучшем случае эквивалентно тому, что мы заплатим всем этим бандитам за то, чтоб они нас пропустили те же 2*x денег. А потому мы просто можем никого не нанимать и заплатить всем — в таком случае ответом на каждый тест будет просто сумма массива и DP не нужно.

Автокомментарий: текст был обновлен пользователем dmkz (предыдущая версия, новая версия, сравнить).

Можно хранить в состоянии суммарное число нанятых бандитов(а сумму видимо ответом динамики). Мы всегда знаем, что это последние бандиты, которых можно было нанять (почему?). То есть по факту нужно решать как будто без ограничения на кол-во бандитов, но при этом при каждом k делать bandits = min(bandits, K[k] + K[k - 1] + K[k - 2])

Auto comment: topic has been translated by dmkz (original revision, translated revision, compare)

Auto comment: topic has been updated by dmkz (previous revision, new revision, compare).

struct orcState {

The following C++17 solution may have a reasonable execution time.

#include <bits/stdc++.h>

using namespace std;

struct hired_t
{
    int battles, size;

    hired_t( int s ) : battles( 3 ), size( s ) {}
};

typedef vector< hired_t > vector_t;

struct state_t: vector_t
{
    int cost, passed, hired;

    state_t( int c = 0, int p = 0, int h = 0 ) : cost( c ), passed( p ), hired( h ) {}

    bool operator < ( const state_t &s ) const
    {
        if ( cost != s.cost )
            return ( cost < s.cost );

        if ( passed != s.passed )
            return ( passed < s.passed );

        return hired > s.hired;
    }

    void battle( int t )
    {
        int u; stack< vector_t::iterator > erased;

        for( auto it = begin(), iu = end(); it != iu; it++, t -= u, hired -= u )
            if ( ( it->size -= ( u = min( t, it->size ) ) ) == 0 || --(it->battles) == 0 )
            {
                erased.push( it );

                if ( it->size > 0 )
                    hired -= it->size;
            }

       while( !erased.empty() )
            erase( erased.top() ), erased.pop();
    }

    void hire( int t )
    {
        emplace_back( t ), hired += t;
    }

} initial_state;

struct states_t: set< state_t >
{
    int min_cost, N, next; struct group_t { int size, cost; } g, group[ 20 ];

    states_t(): min_cost( INT_MAX )
    {
        cin >> N, insert( initial_state );

        for( int i = 0; i < N; i++ )
            cin >> group[ i ].size >> group[ i ].cost;
    }

    void update( const state_t &present )
    {
        if ( present.cost >= min_cost )
            return;

        min_cost = present.cost;

        for( auto it = rbegin(); it != rend() && it->cost > min_cost; it = rbegin() )
            erase( find( *it ) );
    }

    void save( const state_t &present )
    {
        if ( present.cost < min_cost )
            insert( present );
    }

    void battle( state_t present )
    {
        if ( present.passed < N )
            present.battle( g.size ), save( present );
        else
            update( present );
    }

    void pass( state_t present )
    {
        present.cost += g.cost;

        if ( present.passed < N )
            save( present );
        else
            update( present );
    }

    void hire( state_t present )
    {
        present.cost += 2 * g.cost, present.hire( g.size ), save( present );
    }

    void iterate()
    {
        auto it = begin(); state_t present( *it );

        erase( it ), g = group[ present.passed++ ];

        if ( present.hired >= g.size )
            battle( present );

        pass( present );

        if ( present.passed < N )
            hire( present );
    }
};

int main()
{
    ios_base::sync_with_stdio( false ), cin.tie( nullptr ), cout.tie( nullptr );

    int T; cin >> T;

    while( T-- )
    {
        states_t states;

        while( !states.empty() )
            states.iterate();

        cout << states.min_cost << '\n';
    }
}

The following Solution seems to have a reasonable execution time.

Starting with a set of candidate partial solutions that contains a null initial state and an INT_MAX upper bound for the minimum cost, the required solution is the value of the upper bound when the set of partial solutions is empty. The iterative progress through the groups adds a new partial solution to the set only if its present cost is less than the present upper bound.

Hope that this helps.