mahmoud-a
8/25/2017 - 5:44 PM

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

``````#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;
}
``````