题目大意：
有两个数组\(S\),\(T\)，你可以把S进行复制并接到其后面形成\(S^k\)，如\(S\)=123,则\(S^2\)=123123,\(S^3\)=123123123
让你求出\(S^k\)与\(T\)的最长公共子序列以及在最长公共子序列最长时\(k\)的最小值
首先思考如果无视\(k\)最小的要求，最长公共子序列应该是多少
设\(T_i\)表示\(T\)的第\(i\)个元素
对于每个\(T_i\),如果\(S\)中存在\(T_i\)，则将其放入子序列中一定最优，如果\(S\)中不存在\(T_i\)，则\(T_i\)一定不会在公共子序列中
所以对于\(S\)和\(T\)都只保留共有元素，则剩下的\(T\)中每一个元素都应该在最长上升子序列中
于是可以得出最长上升子序列，只需将其放入\(S^k\)即可
\(可以对于每个元素，储存下它在S中每次出现的位置\)
接着遍历\(T\)数组，用\(now\)表示上一个数字在\(S\)填的位置，于是只需找到这个元素最前面能填下的位置即可
如果这个元素不管怎么填都在\(now\)后面，则向后面额外添加一个\(S\),并将其放在最先能放下的地方
查找可以放下的位置可以二分查找,总复杂度\(O(nlogn+m)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int s1[N];
int a[N],b[N];
int c[N],d[N];
int top1,top2;
int n,m,c1,c2;
vector<int> wei[N];
signed main()
{
cin>>n>>m>>c1>>c2;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s1[a[i]]=1;
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
if(s1[b[i]])
s1[b[i]]=2;
}
for(int i=1;i<=n;i++)
{
if(s1[a[i]]==2)
{
wei[a[i]].push_back(i);
}
}
for(int i=1;i<=m;i++)
{
if(s1[b[i]]==2)
d[++top2]=b[i];
}
int now=0,ans=1;
for(int i=1;i<=top2;i++)
{
int nt=lower_bound(wei[d[i]].begin(),wei[d[i]].end(),now+1)-wei[d[i]].begin();
if(now>=wei[d[i]][wei[d[i]].size()-1])
{
ans++;
now=wei[d[i]][0];
}
else
{
now=wei[d[i]][nt];
}
}
cout<<c1*top2<<' '<<c2*ans;
return 0;
}