Un saluto a tutti!
Sono in difficoltà con il problema “esame”; in pratica la soluzione che do passa tutti i subtask tranne il #3, #6 e #11. RIsultato: 10/100.
La soluzione credo essere in programmazione dinamica. Calcolo quindi le soluzioni ottimali per un esame con solo il prof 0, con 0 e 1 (il massimo fra i due), per i successivi parte l’algoritmo “dinamico” calcolando il massimo fra la soluzione dinamica già calcolata fino al prof precedente (senza considerare il corrente) e la somma fra il prof corrente e la dinamica di due indici prima.
Arrivati all’ultimo elemento bisogna tenere in considerazione il primo elemento, in modo che non compaiano entrambi. Tengo un vettore di bool assieme alle soluzioni dinamiche per ricordarmi se la soluzione ad indice i contiene o meno l’elemento ad indice 0; arrivato all’ultimo indice mi regolo di conseguenza.
Temo di essermi spiegato in modo poco comprensibile, però stasera non mi riesce di meglio se qualcuno avesse già risolto, o avesse idee, sarebbe assai gradito. Per completezza incollo il codice
#include <cstdio>
#include <vector>
#define MAXN 1000
FILE * fr, * fw;
int teacher[MAXN];
int n = 0;
int solve(){
int dynamic[n];
dynamic[0] = teacher[0];
std::vector<bool> first_used (n, true);
if (teacher[0] > teacher[1])
dynamic[1] = teacher[0];
else{
dynamic[1] = teacher[1];
first_used[1] = false;
}
int i;
for (i = 2; i<n-1; i++){
if (dynamic[i-1] > dynamic[i-2]+teacher[i]){
dynamic[i] = dynamic[i-1];
first_used[i] = first_used[i-1];
}
else{
dynamic[i] = dynamic[i-2]+teacher[i];
first_used[i] = first_used[i-2];
}
}
//check if i-2 uses first element
if (first_used[i-2]){
//maximum between: i-1, i-2 with last, i-2 with first
if (dynamic[i-1] >= dynamic[i-2]+teacher[i]-teacher[0] &&
dynamic[i-1] >= dynamic[i-2]){
// use i-1
dynamic[i] = dynamic[i-1];
}
else if (dynamic[i-2] >= dynamic[i-1] + teacher[i] - teacher[0]){
//use i-2 with first
dynamic[i] = dynamic[i-2];
}
else{
//use i-2 without first, with last
dynamic[i] = dynamic[i-2] + teacher[i] - teacher[0];
}
}
else{
//first element not used in optimal solution - execute loop one more time
if (dynamic[i-1] > dynamic[i-2]+teacher[i]){
dynamic[i] = dynamic[i-1];
first_used[i] = first_used[i-1];
}
else{
dynamic[i] = dynamic[i-2]+teacher[i];
first_used[i] = first_used[i-2];
}
}
int max_d = -1;
for (int i = 0; i<n; i++){
if (max_d < dynamic[i])
max_d = dynamic[i];
}
return max_d;
}
int main(){
fr = fopen ("input.txt", "r");
fw = fopen ("output.txt", "w");
fscanf (fr, "%d", &n);
for (int i = 0; i<n; i++)
fscanf (fr, "%d", teacher+i);
fprintf (fw, "%d", solve());
fclose (fr);
fclose (fw);
return 0;
}