Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: territoriali.olinfo.it
Per regolare l'accesso alla mostra possiamo far entrare i turisti e le guide in tre modi:
facciamo entrare un turista senza abbinarlo a nessuna guida;
facciamo entrare una guida senza assegnargli nessun turista;
facciamo entrare un turista abbinato ad una guida.
Notiamo che il modo con cui far entrare i turisti e le guide dipende solamente da quanti turisti e guide sono già entrati ma non dipende dall'ordine in cui sono entrati, possiamo quindi risolvere efficientemente questo problema con la programmazione dinamica.
Definiamo come il massimo profitto ottenibile combinando i primi turisti con le prime guide. Notiamo subito che , ovvero possiamo far entrare i primi turisti senza nessuna guida guadagnando 1 euro da ciascuno.
Se possiamo definire ricorsivamente:
facciamo entrare un turista da solo guadagnando euro;
facciamo entrare una guida da sola;
se possiamo far entrare un turista abbinato ad una guida guadagnando euro.
Il valore è quindi il massimo di questi casi. La risposta è .
constexpr int MAXN = 1005;
int dp[MAXN][MAXN];
void solve(int t) {
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];
}
memset(dp, 0, sizeof dp);
for (int i = 0; i < N; i++) {
dp[i][0] = i;
for (int j = 0; j < M; j++) {
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1] + 1);
if(G[j] > V[i]) {
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 2);
}
}
}
cout << "Case #" << t << ": " << dp[N][M] << endl;
}