【codechef】Chef and the Cards（dp，推论）

shawnmei

　　从前有 N 张卡片，在桌上摊成了一排。每张卡片上有两个数字，一个写在上边，一个写在下边，每个数字都是 1 到 N 之间的一个整数（也包含 1 和 N）。同时，在所有卡片的上边的数字中，1 到 N 的每个数字恰好出现了一次。下边的数字也一样。
　　大厨想要给这些卡片重新排个序。他希望在重排之后，卡片上边的数字构成的序列，还有卡片下边的数字构成的序列，这两个序列的最长公共子串尽量长。
　　这里子串的意思是一段连续的子序列。但他不能涂改卡片上的数字，也没法把卡牌倒过来放，也就是说，原本在上边的数字还在上边，下边亦同。
　　请你求出最长公共子串的最大长度。


　　输入格式
　　第一行包含一个整数 T，表示数据组数。接下来是 T 组数据。每组数据的第一行包含一个整数 N。每组数据的第二行包含 N 个整数 A1, A2, . . . , AN，以空格隔开。Ai(1 ≤ i ≤ N) 代表第 i 张卡片上边的数字。每组数据的第三行包含 N 个整数 B1, B2, . . . , BN，以空格隔开。Bi(1 ≤ i ≤ N) 代表第 i 张卡片下边的数字。
　　输出格式
　　对于每组数据，输出一行，包含一个整数 L：最长公共子串的最大长度。
　　


Constraints

• 1 ≤ T ≤ 100
  
• 1 ≤ N ≤ 2000
  
• 1 ≤ Ai, Bi ≤ N
  
• All the elements in both arrays A and B are distinct.
  

Example

Input:
2
3
1 3 2
2 1 3
8
3 8 4 2 6 1 5 7
5 2 4 3 8 7 6 1
Output:
2
4
样例解释　　
　　第一个样例：一种可行的卡牌摆放方法如下：
　　1 2 3
　　2 3 1
　　序列 [1, 2, 3] 与序列 [2, 3, 1] 的最长公共子串是序列 [2, 3]，长度为 2。而以任意其他的方式排列卡牌，都无法得到更长的最长公共子串。故答案为 2。
　　第二个样例：一种可行的卡牌摆放方法如下：
　　7 3 2 8 6 5 4 1
　　1 5 3 2 8 6 4 7
　　最长公共子串为 [3, 2, 8, 6]，长度为 4。说明假设答案为 L。记重排之后处于第 i 位的卡牌的上边的数字为 Ci，下边的数字为 Di。那么，应当存在 x 和 y(1 ≤ x, y ≤ N − L &#43; 1) 满足，对于任意 0 ≤ j < L，都有 Cx&#43;j = Dy&#43;j。


　　
　　http://www.codechef.com/COOK61/problems/CARDLINE


　　英文题解看得好头疼啊。。好在最后还是看懂了。。
　　举一个例子：
　　

7
4 2 6 5 3 7 1  A数组
4 5 6 3 2 1 7  B数组
假如有下标i,j满足Ai==Bj，那么就把这两个下标连起来，最后形成下面的图：　　
　　

____       1-----3
|    |       \   /
0____|        \ /
4
____        ____
|    |      |    |
2____|      5____6
以第二个图为例，　　
　　

A‘ = 2 5 3
B’ = 5 3 2
　　
　　此时的ans=2。
　　假如在AB数组的空隙间插入几个数，变成：
　　

A = 2 x 5 y 3
B = 5 a 3 b 2
如果y==a，那么此时ans=3　　
　　再来引出一个例子：
　　

A = 1 2 3   6 7 8   4 5
B = 2 3 1   7 8 6   5 4
此时可以画出三个图。用上面的思想考虑把这三个图插缝拼起来：　　
　　

A = 1 6 4 2 7 5 3 8
B = 2 7 5 3 8 4 1 6
ans=5　　
　　然而需要注意的是，只有几个两两大小之差<=1的图才能执行上述操作。（为什么？）
　　即只有长度为m或m&#43;1的图才能插缝。（1<=m<=n-1）
　　观察到，插缝时每个图对ans的贡献都是len-1。（上面问题的答案，<=1才能计算贡献&#20540;）
　　然后放出下面这个神奇的DP。。。
　　for(int k=1;k<=nax-1;++k){
for(int i=1;i<=nax-1;++i){
dp[k] = 0;
if(i-k >= 0) dp[k]=max(dp[k], dp[k][i-k] + k - 1);
if(i-k-1 >= 0) dp[k]=max(dp[k], dp[k][i-k-1]+k);
}
}


　　dp[k]的意思是在对限定长度为k(或k&#43;1)插缝后数组总长度为i的情况时最长公共子串长度。这个部分可以预处理。
　　#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define nax 2005
#define ll long long
using namespace std;
int inv[nax];
int a[nax], b[nax];
bool vis[nax];
int t[nax];
int dp[nax][nax];
void te() {
int n;
scanf(&quot;%d&quot;, &n);
for(int i=1;i<=n;++i)
scanf(&quot;%d&quot;, &a);
for(int i=1;i<=n;++i){
scanf(&quot;%d&quot;, &b);
inv[b] = i;
}
for(int i=1;i<=n;++i)
vis = false;
for(int i=1;i<=n;++i){
if(!vis) {
int k = 0;
do {
++k;
vis = true;
i = inv[a];
} while(!vis);
t[k]++;  //最长公共子串长度为k的图有几个
}
}
int r = 0;
for(int i=1;i<=n;++i)
if(a == b)
++r;
for(int k=1;k<=n;++k){
int c = 0;
for(int i=1;i<=n;++i){
c += t * dp[k]; //把原本最长公共子串长度为i的图划分成几个最长公共子串长为k或k+1的图，再计算这些图插缝后总长为i的贡献值，再加到c中，相当于i长度已经插缝好的串再跟c里原本有的这个最长公共子串长度为k或k+1的串插缝，求和即得到最新的最长公共子串长度
}
r = max(r, c);
}
printf(&quot;%d\n&quot;, r);
for(int i=0;i<=n;++i)
t = 0;
}
int main() {
for(int k=1;k<=nax-1;++k){
for(int i=1;i<=nax-1;++i){
dp[k] = 0;
if(i-k >= 0) dp[k]=max(dp[k], dp[k][i-k] + k - 1);
if(i-k-1 >= 0) dp[k]=max(dp[k], dp[k][i-k-1]+k);
}
}
int z;
scanf(&quot;%d&quot;, &z);
while(z--) te();
return 0;
}