Somme di Sequenze 0/100

Ciao a tutti. Ho provato a scrivere una soluzione dp per somme di sequenze. Partendo dalla somma finale di tutti gli elementi del vettore, mano a mano lo divido cercando di trovare le partizioni che minimizzano i picchi di energia. Così, per ciascun sotto-vettore che inizia in i e finisce in j del mio vettore iniziale, il minor picco di energia possibile è il massimo tra:

  • I due sotto-vettore in cui lo ho diviso (in modo ottimale, provandoli tutti e prendendo il minimo)
  • La somma di tutti gli elementi di quel sotto-vettore

Il codice funziona correttamente in tutti i casi di esempio, ma fa 0/100. Ho anche provato a cercare input per cui non funzionasse utilizzando una soluzione brute-force che fa 5/100 e va fuori tempo, ma non ne trovo. Non so più cosa fare, se qualcuno di voi avesse consigli sarebbe di grande aiuto.

#include <bits/stdc++.h>
#include <climits>

using namespace std;

int ans[550][550];

int ricorsiva(vector<int> &v, int x, int y, int somma) {  // y incluso
    // caso base
    if(y-x==0) return 0; // non può essere scelto, è da solo --> non sono state fatte somme, ne tengo conto quando controllo se res<somma sotto
    if(y-x==1) return abs(v[x] + v[y]);

    // ho il res
    if(ans[x][y] != -1) return ans[x][y];

    // calcolo
    int tmp;
    int res = INT_MAX;
    int somma_tmp = somma;
    for(int i=x; i<y; i++) {
        // calcolo il risultato ricorsivamente per ciascun prefisso del vettore e la parte che ne rimane
        somma_tmp -= v[i];
        tmp = max(ricorsiva(v, x, i, somma-somma_tmp), ricorsiva(v, i+1, y, somma_tmp));
        // scelgo la divisione che porta il risultato migliore
        if(tmp<res) res = tmp;
    }
    
    // tengo conto della somma fatta in questo punto della ricorsione (quella tra le due parti dell'array che ho guardato separatamente)
    ans[x][y] = max(res, abs(somma));
    return ans[x][y];
}

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

    int N;
    cin >> N;

    for(int i=0; i<=N; i++) {
        for(int j=0; j<=N; j++) ans[i][j] = -1;
    }
    vector<int> v(N);
    int somma;
    for(int i=0; i<N; i++) {
        cin >> v[i];
        somma += v[i];
    }
    cout << ricorsiva(v, 0, N-1, somma);
}```

Nel main inizializza somma a 0 e il tuo codice fa 100

1 Mi Piace

Grazie mille!!
Avrò riletto il codice decine di volte ma mi era completamente sfuggito :).