|
【题目描述】：王子和公主 一个王子和公主在n*n的格子中行走，这些格子是有1....n^2的编号的。现在给定p+1个数，再给定q+1个数，公主和王子可以选择其中某些格子行走，求他们最多能走几个相同的格子。 |
|
【算法分析】： 这道题读题是关键，然后我们发现需要的是公共的格子，又需要是这个步数最大化，可以想到最长公共子序列的模型。序列长度小于等于62500，最长公共子序列复杂度是n^2，超时。然而可以巧妙的将LCS转化为LIS，使用nlogn的方法求解 |
解题思路：本题是一道经典的题目，巧妙的将LCS问题转化为LIS问题。这种题目的一个特定就是其中一个序列的所有元素均不相同。首先，我们可以对A数组重新编号为{1,2,3,...n}，接下来对于B数组的每个元素，替换为A中那个元素的编号，若没有在A中出现，那么直接置0，这样，B数组也变为一个由编号构成的数组，此时我们发现，A数组是一个自然序列，那么只要在B中找到最长上升的子序列，就是和A的最长公共子序列！这就是本题的巧妙之处！而LIS问题有O(N*logN)的解法，因此可以通过本题的数据规模。
为什么呢？
A‘中为A中元素的代号 即 它们的顺序号
B‘中为B中元素对应的代号（为了分析方便，这里将B中有而A中没有出现的去掉，等价于置0）
因为去掉了B中有而A中没有出现的，所以B‘中的代号全部对应A中的数
设B‘的一个子集p，那么将p由代号翻译成原来数字后一定是A的一个子集（不过在A中顺序不确定）
B‘的LIS时B‘中一个上升的子集 即 顺序号上升的子集 即 该子集在A中是按从左到右的顺序的
所以它是A与B的公共子序列
又因为LIS最长，所以公共子序列最长 即 最长公共子序列
#include<iostream> #include<cstring> #define Max_n 300 using namespace std; int a[Max_n*Max_n],b[Max_n*Max_n]; int f[Max_n*Max_n]; int n,p,q; int lable[Max_n*Max_n]; int LIS(){ f[1]=1; int num=0; for(int i=2;i<=q+1;i++){ for(int j=1;j<i;j++) if(b[j]<b[i]){ f[i]=max(f[i],f[j]+1); } num=max(num,f[i]); //cout<<i<<‘:‘<<f[i]<<endl; } return num; } int main(){ memset(lable,0,sizeof(lable)); freopen("27.in","r",stdin); int x; cin>>n>>p>>q; for(int i=1;i<=p+1;i++){ cin>>x; if(lable[x]==0){ lable[x]=i; } a[i]=lable[x]; //cout<<a[i]<<‘ ‘; } //cout<<endl; for(int i=1;i<=q+1;i++){ cin>>x; b[i]=lable[x]; //cout<<b[i]<<‘ ‘; } //cout<<endl; int ans=LIS(); cout<<ans; fclose(stdin); return 0; }
原文：http://www.cnblogs.com/FuTaimeng/p/5410465.html