Code: Select all
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef struct nodex
{
int v;
int z;//index
}node;
enum xyz {u,d,l};
node wt[10000];
node iq[10000];
int lcs[10000][10000];
xyz dir[10000][10000];
bool iq_sort(node a, node b)
{return a.v < b.v; }
bool wt_sort(node a, node b)
{return a.v > b.v; }
main()
{
int k = 1,mlis = 0,mind = -1;
wt[0].v = -1;
iq[0].v = -1;
wt[0].z = -1;
iq[0].z = -1;
while(scanf("%d %d", &wt[k].v, &iq[k].v)!=EOF)
{
wt[k].z = k;
iq[k].z = k;
k++;
}
sort(wt+1,wt+k,wt_sort);
sort(iq+1,iq+k,iq_sort);
for(int i = 0;i<k;i++)
{
lcs[i][0] = 0;
lcs[0][i] = 0;
dir[0][i] = u;
dir[i][0] = u;
//cout<<arr1[i]<<" "<<arr2[i]<<endl;
}
for(int i = 1;i<k;i++)
{
for(int j = 1;j<k;j++)
{
if(wt[i].z == iq[j].z)
{
lcs[i][j] = lcs[i-1][j-1] + 1;
dir[i][j] = d;
}
else if(lcs[i-1][j] >= lcs[i][j-1])
{
lcs[i][j] = lcs[i-1][j];
dir[i][j] = u;
}
else
{
lcs[i][j] = lcs[i][j-1];
dir[i][j] = l;
}
}
}
/*for(int i = 1;i<k;i++)
{
for(int j = 1;j<k;j++)
cout<<lcs[i][j]<<dir[i][j]<<" ";
cout<<endl;
}*/
printf("%d\n", lcs[k-1][k-1]);
int p = k-1,q = k-1;
while(p > 0 && q > 0)
{
if(dir[p][q] == d)
{
printf("%d\n", wt[p].z);
p--;
q--;
}
else if(dir[p][q] == u)
p--;
else
q--;
}
//system("pause");
}
