Sto provando a risolvere il problema “pianostudi”, solo che non riesco ad ottenere il 100/100 perchè il mio algoritmo va in timeout nel subtask 5. Non riesco a pensare a una soluzione più efficiente di O(n^2). Da quanto mi sembra di aver capito potrebbe essere risolto in maniera greedy con dei Fenwick tree oppure con la programmazione dinamica, solo che non riesco a pensare a nessuna delle due. Il codice che ho implementatio io è questo:
#include<bits/stdc++.h>
using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
struct three{
int da;
int a;
int crediti;
};
bool compare(const three &A, const three &B)
{
if(A.a<B.a)
return true;
if(A.a>B.a)
return false;
if(A.da<B.da)
return true;
return false;
}
int main()
{
int n;
fin>>n;
vector<three> esami(n);
vector<int> crediti(n, 0);
for(int i=0;i<n;++i)
fin>>esami[i].da>>esami[i].a>>esami[i].crediti;
//dopo aver letto l'input riordino il vettore in base ai tempi di fine esame
sort(esami.begin(), esami.end(), compare);
//inizializzo l'array crediti
for(int i=0;i<n;++i)
crediti[i]=esami[i].crediti;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(esami[i].a<esami[j].da&&crediti[i]+esami[j].crediti>crediti[j])
crediti[j]=crediti[i]+esami[j].crediti;
fout<<*max_element(crediti.begin(), crediti.end())<<"\n";
return 0;
}
Sapendo che un esame ha inizio nel tempo s, puoi combinarlo con tutti gli esami che hanno fine nel range [0, s[.
Ora pensa al tuo ordinamento, cosa garantisce?
sort(esami.begin(), esami.end(), compare);
//inizializzo l'array crediti
for(int i=0;i<n;++i)
crediti[i]=esami[i].crediti;
for(int i=n-1;i>-1;--i)
for(int j=0;esami[j].a<esami[i].da;++j)
if(esami[j].crediti+crediti[i]>crediti[j])
crediti[j]=esami[j].crediti+crediti[i];
fout<<*max_element(crediti.begin(), crediti.end())<<"\n";
L’ho ottimizzato leggermente in questo modo. Non penso di aver afferrato il concetto. Con il codice che ho implementato io penso che l’ordinamento dovrebbe garantirmi la sequenzialità degli esami che posso combinare con quello attuale che sto guardando.
Solo che non riesco ancora ad ottenere 100/100
La sequenzialità è una delle cose da notare. Con l’ordinamento per fine sappiamo che se l’i i-esimo esame ha inizio in s_i, solo gli esami in j con j < i possono essere utilizzati se soddisfano il requisito s_i > e_j .
Per capire quindi a che esami far riferimento, dobbiamo trovare l’ultimo valore per j che soddisfi entrambi i requisti sopra elencati. Per farlo puoi effettuare una ricerca lineare come hai già fatto (causando tle) oppure usufruire dell’ordinamento per effettuare una ricerca binaria.
Ora che sai gli esami a cui puoi far riferimento, devi trovare un modo abbastanza veloce per calcolarti il risultato migliore con cui combinare l’i-esimo elemento.
Ti serve trovare il massimo di un prefisso!