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);
}
