Olinfo/mostra.cpp at main · Nataso08/Olinfo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

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


int solve() {
    int N, M;
    cin >> N >> M;

    int risposta = 0;  // memorizza qui la risposta
    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];
    }

    // codice
    vector<vector<int>> dp (N+1, vector<int> (M+1, 0));

    /*
    - solo visitatore       -> 1 €
    - visitatore + guida    -> 2 €
    - solo guida            -> 0 €
    */

    for (int i=0; i<=N; i++) {          // iterazione visitatori
        for (int j=0; j<=M; j++) {      // iterazione guide
            if (i < N)
                // solo visitatore
                dp [i+1][j] = max (dp[i+1][j], dp[i][j] +1);
            if (i < N && j < M && G[j] > V[i])
                // visitatore + guida
                dp [i+1][j+1] = max (dp[i+1][j+1], dp[i][j] +2);
            if (j < M)
                // solo guida
                dp [i][j+1] = max (dp[i][j+1], dp[i][j]);
        }
    }

    risposta = dp[N][M];

    return risposta;
}

int main() {
    // se preferisci leggere e scrivere da file
    // ti basta decommentare le seguenti due righe:

    freopen("mostra_input_3.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int T, t;
    cin >> T;

    for (t = 1; t <= T; t++) {
        cout << "Case #" << t << ": " << solve() << endl;
    }
}