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);
}```