# La mostra di Mojito - problema 3 territoriali 2020

**URL:** <https://forum.olinfo.it/t/la-mostra-di-mojito-problema-3-territoriali-2020/7564>\
**Category:** Aiuto\
**Created:** [6 Luglio 2022, 4:30pm UTC](https://forum.olinfo.it/t/la-mostra-di-mojito-problema-3-territoriali-2020/7564 "2022-07-06T16:30:18Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jaycodecodecode](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/8baadc/32.png) [@Jaycodecodecode](https://forum.olinfo.it/u/Jaycodecodecode)\
**Post date:** [6 Luglio 2022, 4:30pm UTC](https://forum.olinfo.it/t/la-mostra-di-mojito-problema-3-territoriali-2020/7564/1 "2022-07-06T16:30:19Z")

</div>

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:

```auto
#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?

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [7 Luglio 2022, 12:12pm UTC](https://forum.olinfo.it/t/la-mostra-di-mojito-problema-3-territoriali-2020/7564/2 "2022-07-07T12:12:52Z")

</div>

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](https://it.wikipedia.org/wiki/Memoizzazione) e di informarti in generale sulla programmazione dinamica.

---

<div class="post-metadata">

**Author:** ![Jaycodecodecode](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/8baadc/32.png) [@Jaycodecodecode](https://forum.olinfo.it/u/Jaycodecodecode)\
**Post date:** [7 Luglio 2022, 2:07pm UTC](https://forum.olinfo.it/t/la-mostra-di-mojito-problema-3-territoriali-2020/7564/4 "2022-07-07T14:07:03Z")

</div>

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

```auto
#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