Buongiorno a tutti. Stavo risolvendo MOSTRA con questo codice:
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int trovaGuad(vector<int> &V, vector<int> &G, const int N, const int M, const int i, const int j, vector<vector<int>>& dp){
if(j==M){
return N-i;
}
if(i==N){
return 0;
}
if(dp[i][j] != -1){
return dp[i][j];
}
int a=0,b=0,c=0;
if(G[j]>V[i]){
a = trovaGuad(V, G, N, M, i+1, j+1, dp) + 2;
}
b = trovaGuad(V, G, N, M, i+1, j+1, dp) + 1;
c = trovaGuad(V, G, N, M, i, j+1, dp);
dp[i][j]=max(max(a, b), c);
return dp[i][j];
}
int solve() {
int N, M;
cin >> N >> M;
vector<int> V(N), G(M);
for (int i = 0; i < N; i++) {
cin >> V[i];
}
for (int i = 0; i < M; i++) {
cin >> G[i];
}
vector<vector<int>> dp(N, vector<int>(M, -1));
int risposta = trovaGuad(V, G, N, M, 0, 0, dp);
return risposta;
}
int main() {
// se preferisci leggere e scrivere da file
// ti basta decommentare le seguenti due righe:
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T, t;
cin >> T;
for (t = 1; t <= T; t++) {
cout << "Case #" << t << ": " << solve() << endl;
}
}
Ma il massimo che sono riuscito ad ottenere รจ 5/21. Qualcuno riuscirebbe ad aiutarmi? Ho per caso lasciato qualcosa di banale fuori? Ci sono degli edge case particolari? (tutti gli esempi risultano corretti)
Ringrazio in anticipo.