Problemi con Partita

Aiuto
1

Ciao, stavo cercando di risolvere il problema Partita su Terry, penso si debba risolvere con la DP però non riesco a pensare a nessun approccio risolutivo. Qualcuno riesce a darmi qualche hint?

2

Questo non è decisamente un problema di DP.
Prova a pensare a dove avresti voluto prendere dei rinforzi nel momento in cui resti senza soldatini.

3

Non so se è questo l’approccio che volevi che io utilizzassi però ho scritto il codice seguendo il tuo ragionamento e ho ottenuto 50/50.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void solve(int t) {
    int N;
    int K;
    cin >> N >> K;
    vector<int> R(N);
    for (int i = 0; i < N; i++) cin >> R[i];

    int risposta = 0;
    priority_queue<int> maxK;

    for (int i = 0; i < N; i++)
    {
        if(R[i])maxK.push(R[i]);
        

        if (K == 1 && !maxK.empty())
        {
            K += maxK.top();
            risposta++;
            maxK.pop();
        }
        else if (K == 0)
        {
            risposta = -1;
            break;
        }

        K--;
    }

    cout << "Case #" << t << ": " << risposta << "\n";
}

int main() {
    // Se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}