mahmoud-a
8/26/2017 - 6:30 AM

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

``````#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 = 35;
const int OO = 1e9;

int n;
int a[MAX];
int base[MAX];
int cache[MAX][MAX];

string trim(const string& str)
{
size_t first = str.find_first_not_of(' ');
if (string::npos == first)
{
return str;
}
size_t last = str.find_last_not_of(' ');
return str.substr(first, (last - first + 1));
}

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

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

int main() {
cin>>n;
while(1) {
int z;
lp(i, n) {
cin>>z;
base[z-1] = i+1;
}

string line, foo;
getline(cin, foo);
while(getline(cin, line) && line.length() > 2) {
//cout << line.length() << endl;
clr(cache, -1);
istringstream iss(line);
string x;
int y;
lp(i, n) {
iss>>x;
trim(x);
istringstream iss2(x);
iss2 >> y;
a[y-1] = i+1;
}
cout << maxOrder(0, 0) << endl;
}
//printTestCase();
if(line.length() >= 1) {
istringstream iss3(line);
iss3>>n;
} else {
break;
}
}
return 0;
}
``````