Buongiorno ho scritto una soluzione su due passi con il primo ragionamento che mi è venuto in mente per risolvere il problema Ristorante delle OII di quest’anno, il codice fa solo 27/100.
Ho tentato un approccio classico con bruteforce calcolando tutte le possibili soluzioni e facendo una semplice dp.
La complessità non mi sembra cosi alta da non stare nei 3 sec di TLE, possibile che abbia sbagliato io a calcolarla dato che non sono proprio un esperto xD, però nonostante questo va comunque in TLE.
C’è un modo per ottimizzare questo approccio oppure conviene passare a un altro tipo di approccio?
Questo è il mio codice grazie in anticipo!!
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>>v;
vector<vector<int>>dp;
unordered_map<int,int>m;
int f(int i,int j){
if(i>=3){
return 0;
}
if(j>=n){
return f(i+1,0);
}
if(m[v[i][j]]!=0){
return f(i+1,0);
}
if(dp[i][j]!=-1){
return dp[i][j];
}
m[v[i][j]]++;
int sol1=f(i,j+1)+1;
m[v[i][j]]--;
int sol2=f(i+1,0);
return max(sol1,sol2);
}
int conta(int N, vector<int> &A, vector<int> &P, vector<int> &D){
v.resize(3);
dp.resize(3,vector<int>(N,-1));
n=N;
for(int i=0;i<N;i++){
v[0].push_back(A[i]);
}
for(int i=0;i<N;i++){
v[1].push_back(P[i]);
}
for(int i=0;i<N;i++){
v[2].push_back(D[i]);
}
return f(0,0);
}
Ciao! Innanzi tutto la complessità attuale della tua soluzione dovrebbe essere esponenziale se non sbaglio, infatti non assegni mai il valore corretto a dp[i][j] che resta sempre -1.
Inoltre una dp eseguita in questo modo non risolve il problema, il fatto è che non stai utilizzando abbastanza stati e quando vai a calcolarti ad esempio il valore di dp[1][j] lo stai facendo avendo preso un numero di antipasti del tutto arbitrario, non lo stai calcolando su tutte le possibili scelte dei primi x antipasti.
Ah non mi ero per niente accorto di non aver assegnato il valore alla tabella, sul secondo punto penso di non aver capito, il problema dovrebbe essere che cerco sempre di massimizzare il numero di antipasti che posso prendere? Dimmi se ho frainteso ciò che hai scritto
Mh sì penso che tu stia scegliendo in modo greedy il numero di antipasti presi (ma in realtà anche quello dei primi), mentre dovresti controllare per tutti i possibili valori. Cioè se guardi bene la ricorsiva prima richiama f(0,j+1) finché può quindi quando per la prima volta richiamerai f(1,0) ti calcolerai la risposta avendo preso j antipasti, ma per come hai fatto la dp non te la ricalcolerai più, questo non sarebbe un problema se la scelta dei primi fosse indipendente dalla scelta degli antipasti, purtroppo però non lo è.
Questo non era un problema della soluzione precedente che, non aggiornando mai dp[i][j] finiva per calcolarsi tutte le possibilità, anche se in un tempo spropositato, la soluzione che aggiorna la dp sbaglia anche il secondo caso d’esempio per il motivo che ti ho detto.
Io personalmente sono partito dalla bruteforce in N^3, l’ho ricondotta a una N^2 che poi è diventata una NlogN con l’aiuto di qualche struttura dati, oppure puoi usare il metodo brionix, sicuramente geniale anche se molto ad hoc
