#include #include #include #include #include using namespace std; int pago(int i, int x); vector h; vector c; vector pagato; //pagato[i] = quanto pago per la subsequenza se tengo l'i-esima torre(perchè so che dopo è lei la massima da non superare, quindi avrò già il minor costo della sottosequenza [i+1,N-1]) #define hMAX 1000 #define hMIN 0 #define cMAX 50000 #define cMIN 0 #define NMAX 1000 #define NMIN 0 int N; int main(){ ifstream in ("input.txt"); in >> N; for(int i=0; i> x >> y; h.push_back(x); c.push_back(y); pagato.push_back(0); } in.close(); ofstream out ("output.txt"); out << pago(0,hMAX); out.close(); } int pago(int i, int x){ //fine della ricorsione if(i==N-1){ if(h[i]=x){return c[i]+pago(i+1,x); // se è minore posso decidere }else{ // se è esattemente più piccolo di uno rispetto al massimo presente lo tengo per forza if(h[i]==x-1){ if(pagato[i]==0){return pagato[i]=pago(i+1,h[i]); }else return pagato[i]; // altrimenti }else{ // salvo il caso in cui lo tengo if(pagato[i]==0){ pagato[i]=pago(i+1,h[i]); } // salvo il caso in cui lo demolisco int n=c[i]+pago(i+1,x); // se tenerlo cosata meno decido di tenerlo if(pagato[i]