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