UVa 10192

10192.cpp

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

#define F first
#define S second
#define PB push_back
#define endl '\n'

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

string a, b;
int dp[107][107];

int f(int i, int j) {
    if(i == a.size() || j == b.size())
        return 0;

    if(~dp[i][j]) return dp[i][j];

    if(a[i] == b[j])
        dp[i][j] = f( i + 1, j + 1 ) + 1;
    else
        dp[i][j] = max(f( i+1, j ), f( i, j+1 ));

    return dp[i][j];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int z = 1;
    while(getline(cin, a), a[0] != '#') {
        getline(cin, b);
        memset(dp, -1, sizeof dp);
        cout << "Case #" << z++ << ": you can visit at most "
             << f( 0, 0 ) << " cities." << endl;
    }
    return 0;
}