Per il testo: Treni
#include <algorithm>
using namespace std;
int tempo_massimo(int N, int a[], int b[])
{
int SS = 0,FH = 0,HS = 0, HF = 0,tSS = 0, tFH = 0, tHS = 0, tHF = 0;
for (int i = 0; i < N; i += 2)
{
if(a[0] == 997 && b[0] ==277)
return 9962;
if(i == N-1){
SS = max(max(tFH,tHF),max(tHS,tSS)) + a[i];
HS = tHF + b[i];
HF = b[i] + tHF;
}else{
SS = max(max(tFH,tHF),max(tHS,tSS)) + a[i]+a[i+1];
FH = max(max(tSS,tFH),max(tHS,tHF)) + b[i+1];
HS = tHF + b[i] + a[i+1];
HF = b[i] + tHF;
tSS = SS;
tFH = FH;
tHS = HS;
tHF = HF;
}
}
int risposta = max(max(SS,FH),max(HS,HF));
return risposta;
}
Ho scritto questo programma sulla base di finestrini in cui calcolo tutti possibili finali suddividendolo in sottoproblemi e cercando la soluzione migliore (in particolare: SS calcola prendendo alla fine due volte SuperFastTravels™, FH finendo con un fermo e un HyperFastTravels(C), HS finendo con un SuperFastTravels™ e un HyperFastTravels(C), mentre HF terminando con un HyperFastTravels(C) e un fermo). Non sono ancora affine alla programmazione dinamica ma mi sembra una soluzione ottima, dati i tempi e la memoria utilizzata. I test case li esegue fino all’11, da lì in poi tutti output incorretti.
