Aiuto per The Indispensable Brick (ois_tower)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema The Indispensable Brick.

Il mio codice funziona. Ma è troppo lento per andare sotto 1 secondo. Purtroppo non so come ottimizzarlo qualcuno mi potrebbe aiutare?

Ecco il mio codice:

// NOTE: it is recommended to use this even if you don't understand the following code.

#include <bits/stdc++.h>
using namespace std;

bool isPossible(vector<int> numbers, int S) {
    bool dp[S+1] = {false};
    dp[0] = true;

    for (int number:numbers) {
        for (int j=S; j >= number; j--) {
            if (dp[j-number]) {
                dp[j] = true;
            }
        }
    }

    return dp[S];
}

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");

    int N, S;
    cin >> N >> S;

    vector<int> H(N);
    for (int i = 0; i < N; ++i)
        cin >> H[i];

    vector<bool> ans(N);


    // INSERT YOUR CODE HERE

    for (int i=0; i<N; i++) {
        int number = H[0];
        H.erase(H.begin());
        ans[i] = not isPossible(H, S);
        H.push_back(number);
    }


    for (int i = 0; i < N; ++i) {
        if (ans[i]) {
            cout << "YES";
        } else {
            cout << "NO";
        }

        cout << endl;
    }
    return 0;
}

Grazie mille in anticipo!

2

Ti serve un trucco per evitare di fare knapsack N volte: riesci a riscrivere la condizione come condizione su un prefisso + condizione su un suffisso dell’array?
Se no forse con i bitset passa anche \mathcal{O}(N^2S).

1 Mi Piace