I have applied LCS ( i think its more convinient to apply than LIS here)..
But recieving Wrong answer continously ..I have also taken care of the fact that the input gives the ranking of the events not the actual ordering..??
Can anyone explain where my code is lacking or provide some fresh test data??
- Code: Select all
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class sumant
{
public :
int a[25];
int b[25];
int n,x;
int c[25][25];
void input()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
a[x]=i;
}
while(cin)
{
for(int i=1;i<=n;i++)
{
cin>>x;
b[x]=i;
}
int z=doit();
cout<<z<<endl;
}
}
int doit()
{
for(int i=0;i<=n;i++)
{
c[i][0]=0;
}
for(int i=0;i<=n;i++)
{
c[0][i]=0;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i]==b[j])
{
c[i][j]=c[i-1][j-1]+1;
}
else if(c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
return c[n][n];
}
};
int main()
{
sumant s;
s.input();
return 0;
}
