Sto cercando di risolvere missioni segrete attraverso la programmazione dinamica però la mia idea su come risolvere l’esercizio porta solo ad un 30/100. In sostanza io verifico se posso effettuare una determinata missione e se è possibile cerco di effettuarla dopo ad un gruppo di missioni che sia il più grande possibile in modo tale da massimizzare il numero di missioni effettuate. Alla fine trovo il numero massimo nel vettore miss per ottenere il numero massimo di missioni.
Questo è il codice :
#include <fstream>
#include <iostream>
using namespace std;
int main(){
ifstream in("input.txt");
ofstream out("output.txt");
int n,a,b,cont=0;
in>>n;
int supp[n+1];
int miss[n+1];
miss[0]=0;
supp[0]=0;
for(int i=1;i<=n;i++){
in>>a>>b;
int maxval=0;
int maxcont=0;
for(int j=i-1;j>=0;j--){
if(a+supp[j]<=b){
if(maxcont<miss[j]+1){
maxcont=miss[j]+1;
maxval=a+supp[j];
}
}
}
supp[i]=maxval;
miss[i]=maxcont;
}
int max=miss[0];
for(int i=1;i<=n;i++){
if(max<miss[i]){
max=miss[i];
}
}
out<<max;
}