题目大意：
有两个数组 \(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\) 即可。
求 \(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;
}