# Aiuto mostra di mojito

**URL:** <https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189>\
**Category:** Aiuto\
**Created:** [15 Aprile 2023, 8:16pm UTC](https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189 "2023-04-15T20:16:50Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![jvsx](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/b782af/32.png) [@jvsx](https://forum.olinfo.it/u/jvsx)\
**Post date:** [15 Aprile 2023, 8:16pm UTC](https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189/1 "2023-04-15T20:16:50Z")

</div>

Sono abbastanza nuovo e non so ancora programmare e usare il c++ a livello decente quindi non so come si faccia a usare un metodo ricorsivo o dividi et impera, come la maggior parte delle persone che caricano il codice suggerisce di fare, quindi, visto che questo codice mi da 7/21 al massimo su terry, qualcuno ha dei suggerimenti su come migliorarlo? O su eventuali problemi? Grazie mille.

```auto
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int MAXN = 1000;
const int MAXM = 1000;

int solve(int t) {
    int N, M;
    cin >> N >> M;
		
    int risposta = 0; 
    vector<unsigned long long> V(N), G(M);
	int x;
    for (int i=0; i<N; i++) {
        cin >> V[i];
    }
    for (int i=0; i<M; i++) {
        cin >> G[i];
	}
	int app, i=0, pos, posp=0, pos1=0;
	bool Found=false;
	for(int g=0;g<M;g++){
		int maxG=G[g], maxV=V[i];
		for(int n=1;n<N-i;n++){
			if(maxV<V[i+n])
				maxV=V[i+n];
		}
		for(int n=1;n<M-g;n++){
			if(maxG<G[g+n]){
				maxG=G[g+n];
				posp=g+n;
			}
		}
		for(int m=1;m<M-g;m++){
			if(G[g]<G[g+m]){
				pos=g+m;
				break;
			}
		}
		//cout<<G[pos]<<" "<<maxG<<" "<<maxV<<" "<<i<<" "<<g<<" "<<V[i]<<" "<<G[g]<<" "<<risposta<<endl;
		if(G[g]>V[i]){
			if(G[i]!=maxG || V[i]!=maxV)
				risposta=risposta+2;
			
			if(G[i]==maxG && V[i]==maxV)
				risposta=risposta+2;
		}
		else if(G[g]<=V[i]){

			if(G[g]>G[g+1] && G[g]>V[i+1] && i+1<N && g+1<M){
				risposta=risposta+3;
				i++;
				//cout<<"ci sono"<<endl; 			
			}		
			else if(G[g]<=G[g+1] && g+1<M && i+1<N){	
				if(G[g]>V[i+1] && G[pos]<V[i] && G[g+1]<V[i] && M-g<=N-i){
					risposta=risposta+3;
					i++;
					//cout<<"4"<<endl;
				}	
				else if(G[pos]>V[i] && M-pos>=N-i){
					risposta=risposta+2;
					g=pos;
					//cout<<"1"<<endl;
				}
				else if(G[pos]<V[i]){
					for(int m=1;m<M-g;m++){
						if(G[g+m]>V[i] && M-(g+m)>=N-i){
							pos1=g+m;
							Found=true;
							break;
						}
					}
					if(Found==true){
						risposta=risposta+2;
						g=pos1;
					}
					else if(maxG>V[i] && M-posp>=N-i){
						g=posp;
						risposta=risposta+2;
					}
					else /*if(G[g]>V[i+1] || G[pos]<V[i])*/{
						risposta++;
						g--;
					}
					//cout<<"5"<<endl;			
				}
				else if(maxG>V[i] && M-posp>=N-i){
					g=posp;
					risposta=risposta+2;
					//cout<<"2"<<endl;
				}
				else /*if(G[g]>V[i+1] || G[pos]<V[i])*/{
					risposta++;
					g--;
					//cout<<"3"<<endl;
				}
				//cout<<"ci sono 2"<<endl;
			}
			else{
				//cout<<"ci sono 3"<<endl;
				i--;
			}	
		}
		i++;
		app=i;
		Found=false;
		if(i>=N)
			break;
	}

	for(int i=0;i<N-app;i++){
		risposta++;
	}
	
    cout << "Case #" << t << ": " << risposta<< endl;
}

int main() {
    
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T;
    cin >> T;

    for (int t = 1; t <=T; t++) {
    	//cout<<T<<" "<<t<<endl;
        solve(t);
    }
}

```

---

<div class="post-metadata">

**Author:** ![fabriziogiacomi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fabriziogiacomi/32/2523_2.png) [@fabriziogiacomi](https://forum.olinfo.it/u/fabriziogiacomi)\
**Post date:** [15 Aprile 2023, 10:32pm UTC](https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189/2 "2023-04-15T22:32:40Z")

</div>

Ciao, potresti spiegare – a grandi linee – cosa fa il tuo codice?  
Piccolo suggerimento: questo problema è risolvibile attraverso la _programmazione dinamica_. Se sei nuovo al C++, ti consiglio di usare la piattaforma [AlgoBadge](https://algobadge.olinfo.it), che offre un percorso lineare (e se partecipi alle nazionali devi anche raggiungere il badge d’argento!).

Se sai cos’è la programmazione dinamica, ragiona sugli stati che può assumere il problema:

- 

Entra un visitatore da solo

- 

Entra un visitatore con la guida

- 

Entra una guida da sola

Quindi puoi stabilire per ognuna il guadagno e calcolare nella tabella la soluzione ottimale.

Spero di essere stato d’aiuto, buona serata e buona fortuna!

---

<div class="post-metadata">

**Author:** ![jvsx](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/j/b782af/32.png) [@jvsx](https://forum.olinfo.it/u/jvsx)\
**Post date:** [16 Aprile 2023, 6:26am UTC](https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189/3 "2023-04-16T06:26:35Z")

</div>

Non so tanto della programmazione dinamica, però ci proverò. Grazie mille per il suggerimento.

---

<div class="post-metadata">

**Author:** ![fabriziogiacomi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fabriziogiacomi/32/2523_2.png) [@fabriziogiacomi](https://forum.olinfo.it/u/fabriziogiacomi)\
**Post date:** [16 Aprile 2023, 6:50am UTC](https://forum.olinfo.it/t/aiuto-mostra-di-mojito/8189/4 "2023-04-16T06:50:17Z")

</div>

Prego, se ti serve una mano a capire la programmazione dinamica in questo problema, la wiki delle Olimpiadi fornisce una soluzione molto dettagliata al problema:  
[https://wiki.olinfo.it/it/2020/territoriali/mostra](https://wiki.olinfo.it/it/2020/territoriali/mostra)

Se avessi bisogno di chiarimenti, chiedi pure 🙂