Esame di maturità (ABC 2016)

Aiuto
1

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

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

vector<int>D(MAXN);
valarray<int>solve(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();
}
2

Ciao, la strategia risolutiva non è quella corretta. Dovresti trovare una soluzione che sfrutti la programmazione dinamica, riducendo la complessità a O(N).

3

Hai qualche suggerimento per implementare una soluzione in DP?

4

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.

6

Ho cercato di ascoltare il tuo consiglio e scopiazzando un po’ da internet :slight_smile: 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.

#include <iostream>
#include <vector>
#define MAXN 100000
using namespace std;

int N;
vector<int>D(MAXN);
vector<int>temp(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;
}
7

Prova con questo input:

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

8

grazie mille