https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1007

10066 - The Twin Towers.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 105;
const int OO = 1e9;

int cache[MAX][MAX];
int a[MAX], b[MAX];
int n1, n2;

int maxTower(int i, int j) {
    if(i == n1 || j == n2)
        return 0;
    int &ret = cache[i][j];
    if(ret != -1)
        return ret;
    ret = -1*OO;
    int ch0 = -1*OO;
    if(a[i] == b[j])
        ch0 = 1 + maxTower(i+1, j+1);
    int ch1 = maxTower(i+1, j);
    int ch2 = maxTower(i, j+1);

    return ret = max(max(ch0, ch1), ch2);
}

int main() {
    cin>>n1>>n2;
    int k = 1;
    while(n1 != 0 && n2 !=0) {
        clr(cache, -1);
        lp(i, n1)
            cin>>a[i];
        lp(i, n2)
            cin>>b[i];
        cout << "Twin Towers #" << k << endl;
        cout << "Number of Tiles : " << maxTower(0, 0) << endl << endl;
        k++;
        cin>>n1>>n2;
    }
    return 0;
}