Poj Solution 1692

http://poj.org/problem?id=1692

#include<iostream>
using namespace std;
int links[101][101];
int f[101],s[101],n,m;
int answer;

void find()
{int i,j,t,k,h;
    links[0][0]=0;
    links[0][1]=0;
    links[1][0]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{t=links[i-1][j]>links[i][j-1]?links[i-1][j]:links[i][j-1];
 if(f[i]!=s[j])
 {
 for(k=i-1;k>=1;k--)
     if(f[k]==s[j])break;
 for(h=j-1;h>=1;h--)
     if(f[i]==s[h])break;
 if(k&&h&&links[k-1][h-1]+1>t)t=links[k-1][h-1]+1;
 }
 links[i][j]=t;
}
}


int main()
{int i,t;
    cin>>t;
    while(t--)
    {cin>>n>>m;
        for(i=1;i<=n;i++)cin>>f[i];
        for(i=1;i<=m;i++)cin>>s[i];
        find();
        cout<<links[n][m]*2<<endl;
    }
return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *