La mostra di Mojito - problema 3 territoriali 2020

Aiuto
1

Ciao a tutti, sto provando a risolvere il problema MOSTRA (territoriali 2020). Ho implementato una soluzione ricorsiva che funzioni sui testcase di prova e alcuni dell’input, ma con altri entra in un loop infinito e non riesco a capire il perché.
Questo è il codice:

#include <bits/stdc++.h>
using namespace std;

int f(vector<int>& N, vector<int>& M, int n, int m){
  if(n==0) return 0;
  if(m==0) return n;

  int aus = max(f(N,M,n,m-1), f(N,M,n-1,m)+1);
  
  if(N[n-1] >= M[m-1]) return aus;
  else return max(aus, f(N,M,n-1,m-1)+2);
}

int main(){
  int t;
  cin >> t;
  for(int T=1; T<=t;T++){
    int n, m;
    cin >> n >> m;
    vector<int> N(n),M(m);
    for(int i=0; i<n; i++) cin >> N[i];
    for(int i=0; i<m; i++) cin >> M[i];
    
    cout << "Case #" << T << ": " << f(N,M,n,m) << endl;
  }
  return 0;
}

Qualcuno sa risolvere?

2

Salve, la tua soluzione non entra in loop, ma per input grandi richiede troppo tempo.
La tua funzione ricorsiva viene chiamata con gli stessi parametri diverse volte ed è costretta a ricalcolare risultati già calcolati. Cerco un modo per salvare questi risultati e restituirli se già calcolati.
Ti consiglio di leggere questo articolo sulla memoizzazione e di informarti in generale sulla programmazione dinamica.

4

Grazie ai tuoi consigli sono riuscito a risolvere, grazie mille.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1002;
int memo[mxN][mxN];

int f(vector<int>& N, vector<int>& M, int n, int m){
  if(n==0) return 0;
  if(m==0) return n;
  if(memo[n][m] == -1){
    int aus = max(f(N,M,n,m-1), f(N,M,n-1,m)+1);
    if(N[n-1] >= M[m-1]) memo[n][m] = aus;
    else memo[n][m] = max(aus, f(N,M,n-1,m-1)+2);
  }
  return memo[n][m];
}

int main(){
  int t;
  cin >> t;
  for(int T=1; T<=t;T++){
    int n, m;
    cin >> n >> m;
    memset(memo,-1,sizeof memo);
    vector<int> N(n),M(m);
    for(int i=0; i<n; i++) cin >> N[i];
    for(int i=0; i<m; i++) cin >> M[i];
    
    cout << "Case #" << T << ": " << f(N,M,n,m) << endl;
  }
  return 0;
}

In effetti bastava salvare le risposte

1 Mi Piace