# Esame di maturità (ABC 2016) **URL:** \ **Category:** Aiuto\ **Created:** [26 Luglio 2022, 1:12pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636 "2022-07-26T13:12:49Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![SBUCCIERI](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/4bbf92/32.png) [@SBUCCIERI](https://forum.olinfo.it/u/SBUCCIERI)\ **Post date:** [26 Luglio 2022, 1:12pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/1 "2022-07-26T13:12:49Z")
Ho cercato di implementare un algoritmo che mi cercasse tutte le possibili combinazioni rispettando le condizioni del problema, il codice fa 10 / 100, sbaglia due output della seconda sub task e tutta la terza, l’idea risolutiva dovrebbe essere giusta ma credo che manchi ancora qualche caso da considerare e non riesco a capire quale sia, grazie in anticipo per l’aiuto ```auto #include #define MAXN 100000 using namespace std; vectorD(MAXN); valarraysolve(MAXN); int N; int main() { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> N; for(int i = 0; i != N; i++) cin >> D[i]; int lastIndex = 0; for(int i = 0; i != N; i++) { solve[i] = D[i]; for(int j = 0; j != N; j++) { if( abs(i - j) >= 2 && abs(lastIndex - j) >= 2 && abs(i - j) != N - 1 && abs(lastIndex - j) != N - 1) { lastIndex = j; solve[i] += D[j]; } } } cout << solve.max(); } ``` ---
**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\ **Post date:** [26 Luglio 2022, 2:08pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/2 "2022-07-26T14:08:04Z")
Ciao, la strategia risolutiva non è quella corretta. Dovresti trovare una soluzione che sfrutti la programmazione dinamica, riducendo la complessità a O(N). ---
**Author:** ![SBUCCIERI](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/4bbf92/32.png) [@SBUCCIERI](https://forum.olinfo.it/u/SBUCCIERI)\ **Post date:** [26 Luglio 2022, 3:45pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/3 "2022-07-26T15:45:00Z")
Hai qualche suggerimento per implementare una soluzione in DP? ---
**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\ **Post date:** [26 Luglio 2022, 4:17pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/4 "2022-07-26T16:17:34Z")
Ti consiglio di cercare su internet “_massima somma di elementi non contigui_” e una volta che capisci la logica lo adatti al contesto del problema. Se non capisci bene chiedi pure, ciao. ---
**Author:** ![SBUCCIERI](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/4bbf92/32.png) [@SBUCCIERI](https://forum.olinfo.it/u/SBUCCIERI)\ **Post date:** [27 Luglio 2022, 10:23am UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/6 "2022-07-27T10:23:23Z")
Ho cercato di ascoltare il tuo consiglio e scopiazzando un po’ da internet 🙂 e cercando di far rispettare le condizioni del problema faccio sempre 10 / 100, ma stavolta risolvo quasi tutti i casi, anche se non riesco a completare le subtask, non riesco a capire quale sia il tassello mancate, spero i un aiuto, grazie in anticipo. ```auto #include #include #define MAXN 100000 using namespace std; int N; vectorD(MAXN); vectortemp(MAXN); int main() { freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); cin >> N; for(int i = 0; i != N; i++) cin >> D[i]; temp[0] = D[0]; temp[1] = max(D[0], D[1]); int K = N; if(temp[1] == temp[0] && D[0] != D[1]) //condizione per la quale se viene preso il primo elemento l'ultimo deve essere escluso K--; else if(D[0] == D[1]) //se i primi due elmementi sono uguali azzero il primo, altrimenti influirebbe nell'incremento del risultato nel ciclo for temp[0] = 0; for (int i = 2; i != K; i++) { temp[i] = max(temp[i - 1], temp[i - 2] + D[i]); temp[i] = max(temp[i], D[i]); } int res; if(K == N - 1) //in base al valore di K il risulutato si sposta quindi lo aggiorno di conseguenza al suo valore res = temp[N - 2]; else res = temp[N - 1]; cout << res; } ``` ---
**Author:** ![MatteoArcari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/matteoarcari/32/1976_2.png) [@MatteoArcari](https://forum.olinfo.it/u/MatteoArcari)\ **Post date:** [27 Luglio 2022, 12:11pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/7 "2022-07-27T12:11:48Z")
Prova con questo input: ```auto 5 5 1 0 3 10 ``` La soluzione ottimale è chiaramente 11 ma il tuo algoritmo restituisce 8. Questo perché considerando a prescindere i primo elemento, in quanto maggiore del secondo, escludi l’ultimo che ti potrebbe dare un risultato migliore. Come strategia ti ci sei avvicinato di più rispetto alla prima soluzione, però la dp andrebbe implementata in maniera leggermente differente. L’approccio corretto consiste nel salvarsi per ogni elemento la soluzione migliore ipotizzando di considerarlo sempre, in relazione alle soluzioni parziali precedenti. Soluzione: Creo due vettori (dp0 e dp1) in cui mi salvo i risultati parziali considerando o meno il primo elemento (in modo da non escludere l’ultimo elemento dalle possibili soluzioni). Questi vettori vanno riempiti tramite la seguente formula: `dp[i]=V[i] + max(dp[i-2], dp[i-3]`). Questo perché considerando ‘dp[i-4]’ posso sempre considerare anche dp[i-2] ottenendo una soluzione migliore, visto che ci sono solo elementi positivi. La soluzione sarà il massimo tra le soluzioni parziali. Spero di essere stato chiaro, in caso non fosse così chiedi pure. Ciao ---
**Author:** ![SBUCCIERI](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/4bbf92/32.png) [@SBUCCIERI](https://forum.olinfo.it/u/SBUCCIERI)\ **Post date:** [27 Luglio 2022, 12:30pm UTC](https://forum.olinfo.it/t/esame-di-maturita-abc-2016/7636/8 "2022-07-27T12:30:58Z")
grazie mille