SOLUZIONE: Ho provato a risolvere il problema utilizzando le soluzioni precedenti, quindi con la bottom up e mi sembra che sia il metodo migliore per risolvere questo problema.
Ciao a tutti, sto cercando di risolvere questo problema, e come primo approccio sto cercando di ottenere qualche punto implementando un algoritmo ricorsivo…
Ecco cui il codice, mi da molti output sbagliati e alcuni corretti, sparsi nei vari subtasks.
#include <iostream>
#include <fstream>
#define MAXN 1000
using namespace std;
struct torre
{
int altezza;
int costo;
};
torre torri[MAXN];
int n;
int alt_prec = 1001;
int costo_tot;
int sol[MAXN];
int minimo_costo_decrescente(int costo,int i,int alt_prec)
{
if(i==n) return costo;
if(torri[i].altezza<alt_prec)
{
return max(minimo_costo_decrescente(costo + torri[i].costo,i+1,torri[i].altezza),
minimo_costo_decrescente(costo,i+1,torri[i].altezza));
}else
return minimo_costo_decrescente(costo,i+1,alt_prec);
}
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
in>>n;
//cout<<"N: "<<n<<endl;
for(int i = 0;i<n;i++)
{
in>>torri[i].altezza;
in>>torri[i].costo;
// cout<<"Torre "<<i<<" : Altezza = "<<torri[i].altezza<<" Costo = "<<torri[i].costo<<endl;
}
for(int i = 0;i<n;i++) costo_tot += torri[i].costo;
//cout<<"Costo Totale: "<<costo_tot<<endl;
//cout<<endl;
/*
cout<<"Costo torri da non demolire : "<<minimo_costo_decrescente(0,0,alt_prec)<<endl;
sol = costo_tot-minimo_costo_decrescente(0,0,alt_prec);
cout<<"Soluzione: "<<sol<<endl;
*/
int mas = -1000000;
for(int i = 0;i<n;i++)
{
sol[i] = minimo_costo_decrescente(0,i,alt_prec);
mas = max(mas,sol[i]);
}
out<<costo_tot-mas;
return 0;
}