sto provando a risolvere questo problema con la programmazione dinamica e se lo provo nel mio computer i test vanno ma se lo provo su olinfo mi dice execution killed.
Questo è il mio codice:
#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> soluzioni(99999999);
vector<bool> abbiamoGia(9999999);
int svolgi(int N, vector<int> T, bool puoiPassare, int luceCorrente)
{
if(luceCorrente>=N)
{
return 0;
}
int tempo1=9999999;
int tempo2=9999999;
//ci fermiamo
tempo1=svolgi(N,T,true,luceCorrente+1)+T[luceCorrente];
//passiamo
if(puoiPassare && luceCorrente<N)
{
if(abbiamoGia[luceCorrente])
{
tempo2=soluzioni[luceCorrente];
}else{
tempo2=svolgi(N,T,false,luceCorrente+1);
soluzioni[luceCorrente]=tempo2;
abbiamoGia[luceCorrente]=true;
}
}
int tempoMigliore=min(tempo1,tempo2);
return tempoMigliore;
}
int main() {
ifstream fin("input.txt");
ofstream fout("output.txt");
int N;
fin >> N;
vector<int> T(N);
for (int i=0; i<N; i++)
fin >> T[i];
int soluzione= svolgi(N,T,true,0);
fout << soluzione << endl; // print the result
return 0;
}