sto provando a fare questo esercizio con la programmazione dinamica ma il mio codice è troppo lento e non riesco a superare i testcase più lunghi
questo è il mio codice:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
int memo[9999][9999]; //i dati memorizzati
bool giaFatto[9999][9999]; //se è memorizzato
int svolgi(int& N,int& M,vector<int>& V,vector<int>& G,int v,int g) // v = posizione del visitatore da guardare g= posizione della guida da guardare
{
if(v>=N) //se finiti visitatori
{
return 0;
}
if(g>=M) //se finite guide
{
return N-v;
}
if(giaFatto[g][v])
{
return memo[g][v];
}
int soldi1=-1,soldi2=-1;
//non assegna guida
soldi1=svolgi(N,M,V,G,v+1,g)+1;
//manda guida da sola
if(g<M && G[g]<=V[v])
{
soldi2=svolgi(N,M,V,G,v,g+1);
}
//assegna guida
if(G[g]>V[v] && g<M)
{
return svolgi(N,M,V,G,v+1,g+1)+2;
}
int massimo=max(soldi1,soldi2);
memo[g][v]=massimo;
giaFatto[g][v]=true;
return massimo;
}
int main()
{
int test;fin>>test;
for(int t=0;t<test;t++)
{
int N,M;fin>>N>>M;
vector<int>V(N);
vector<int>G(M);
for(int i=0;i<N;i++)
{
fin>>V[i];
}
for(int i=0;i<M;i++)
{
fin>>G[i];
}
for(int i=0;i<9999;i++)
{
for(int b=0;b<9999;b++)
{
giaFatto[i][b]=false;
}
}
fout<<"Case #"<<t+1<<": "<< svolgi(N,M,V,G,0,0)<<endl;
}
return 0;
}