題意：給定兩個長度為p+1和q+1的序列，求兩個序列的LCS。

思路：如果直接使用樸素的LCS算法則O（pq）會超時，可以把A中出現的元素編碼，然后映射到B（只保留AB都存在的元素），這樣就轉化為求B的LIS問題了O（nlogn）。

code：

#include <bits/stdc++.h> using namespace std;const int N=250*250; const int INF=0x3f3f3f3f;int s[N],f[N],d[N],id[N];int main() {int T;scanf("%d",&T);for (int ca=1;ca<=T;ca++){int N,p,q,x;scanf("%d%d%d",&N,&p,&q);memset(id,0,sizeof(id));for (int i=1;i<=p+1;i++) {scanf("%d",&x);id[x]=i;}int n=0;for (int i=0;i<q+1;i++){scanf("%d",&x);if (id[x]) s[n++]=id[x];}for (int i=1;i<=n;i++) f[i]=INF;int ans=0;for (int i=0;i<=n;i++){int p=lower_bound(f+1,f+n+1,s[i])-f;d[i]=p;f[p]=s[i];ans=max(ans,d[i]);}printf("Case %d: %d\n",ca,ans);}}

總結

以上是生活随笔為你收集整理的UVA 10635——Prince and Princess的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。