# LCS

Time Limit: 1 Sec

Memory Limit: 256 MB

## 题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5495

## Description

你有两个序列\{a_1,a_2,...,a_n\}{a?1??,a?2??,...,a?n??}和\{b_1,b_2,...,b_n\}{b?1??,b?2??,...,b?n??}. 他们都是11到nn的一个排列. 你需要找到另一个排列\{p_1,p_2,...,p_n\}{p?1??,p?2??,...,p?n??}, 使得序列\{a_{p_1},a_{p_2},...,a_{p_n}\}{a?p?1????,a?p?2????,...,a?p?n????}和\{b_{p_1},b_{p_2},...,b_{p_n}\}{b?p?1????,b?p?2????,...,b?p?n????}的最长公共子序列的长度最大.

## Input

输入有多组数据, 第一行有一个整数TT表示测试数据的组数. 对于每组数据:

## Output

对于每组数据, 输出LCS的长度.

## Sample Input

2
3
1 2 3
3 2 1
6
1 5 3 2 6 4
3 6 2 4 5 1

Sample Output

2
4

## HINT

#include<iostream>
#include<stdio.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;

int a[100500];
int b[100500];
int c[100500];
int vis[100500];
int main()
{
int n;
int t;scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
vis[i]=0;
}
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
c[a[i]]=b[i];
int ans = n;
for(int i=1;i<=n;i++)
{
int x=i;
if(vis[x])continue;
if(c[x]!=x)
{
ans--;
while(!vis[x])
{
vis[x]=1;
x=c[x];
}
}
}
printf("%d\n",ans);
}
}

## HDU 2092 整数解 --- 水题

x+y = n, x*y = m; y = n - x; x * ( n - x) = m nx - x^2 = m; x^2 - nx + m = 0; △ = sqrt(n^2 - 4m) 要有整数解即△需要为可开方数即可. /* HDU 2092 整数解 --- 水题 */ #include <cstdio> #include <cmath> int main() { double n, m; while (scanf("%lf%lf", &n,

## hdu 5210 delete 水题

Delete Time Limit: 1 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=5210 Description wld有n个数(a1,a2,...,an),他希望进行k次删除一个数的操作,使得最后剩下的n−k个数中有最多的不同的数,保证1≤n≤100,0≤k<n,1≤ai≤n(对于任意1≤i≤n) Input 多组数据(最多100组)对于每组数据:第一行:一个数n表示数的个数接下来一行:

## hdu 4802 GPA 水题

GPA Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4802 Description In college, a student may take several courses. for each course i, he earns a certain credit (ci), and a mark ranging from A to F, which is c

## hdu 5326 Work 水题

Work Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 225    Accepted Submission(s): 166 Problem Description It’s an interesting experience to move from ICPC to work, end my college life and star

## hdu 4493 Tutor 水题

Tutor Time Limit: 20 Sec  Memory Limit: 256 MB 题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=4493 Description Lilin was a student of Tonghua Normal University. She is studying at University of Chicago now. Besides studying, she worked as a tutor tea