NC17683. Longest Common Subsequence
描述
输入描述
The first line contains one integer, which is n.
The second line contains n integers, which is the sequence {ai}.
The third line contains n integers, which is the sequence {bi}.
The fourth line contains n integers, which is the sequence {ci}.
The fifth line contains n integers, which is the sequence {di}.
1 <= n <= 10000
1 <= ai <= n
Any number appears in {ai} at most 2 times.
1 <= bi <= n
Any number appears in {bi} at most 2 times.
1 <= ci <= n
Any number appears in {ci} at most 2 times.
1 <= di <= n
输出描述
You should output one integer, which is the length of the LCS.
示例1
输入:
5 1 2 1 2 3 1 2 3 1 2 3 1 2 1 2 1 2 1 2 1
输出:
4
C++11(clang++ 3.9) 解法, 执行用时: 252ms, 内存消耗: 1500K, 提交时间: 2018-08-16 17:04:31
#include<bits/stdc++.h>
#define N 10010
#define mod 1000000007
using namespace std;
int n,m;
int s[3][N],ps[N][2][3],t[N];
int f[N][8],ded[N][8];
int main()
{
// freopen("G.in","r",stdin);
int i,j,k,l,r;
scanf("%d",&n);
for(k=0;k<3;k++)
for(i=1;i<=n;i++)
scanf("%d",&s[k][i]);
for(i=1;i<=n;i++)scanf("%d",&t[i]);
for(k=0;k<3;k++)
{
for(i=1;i<=n;i++)
{
j=s[k][i];
if(ps[j][0][k])ps[j][1][k]=i;
else ps[j][0][k]=i;
}
}
int pos[3];
bool flag;
for(i=1;i<=n;i++)for(k=0;k<8;k++)
{
for(j=i-1;j+1&&i-j<=100;j--)for(l=0;l<8;l++)if(f[j][l]+1>f[i][k])if(!ded[j][l])
{
flag=1;
for(r=0;r<3;r++)
{
if(ps[t[i]][(k>>r)&1][r]
<=ps[t[j]][(l>>r)&1][r])
flag=0;
}
if(flag)f[i][k]=f[j][l]+1;
}
for(j=0;j<k;j++)
{
if((k&j)==j&&f[i][k]<=f[i][j])
{
ded[i][k]=1;
break;
}
}
}
int ans=0;
for(i=1;i<=n;i++)for(j=0;j<8;j++)ans=max(ans,f[i][j]);
printf("%d\n",ans);
return 0;
}