Description
有两个数组 \(A,B\) ,我们可以将 \(A\) 数组无限次重复拼接。求最少需要多少次拼接使得拼接后的 \(A,B\) 的最长公共子序列最大。
Analysis
我们要学会从题目中找到一些信息，比如说本题的数据范围：
对于 \(100\%\) 的数据，保证 \(1\leq n,m,S_i,T_i\le 10^6\)，\(c_1,c_2 \in \{0,1\}\)。
我们知道朴素dp求LCS的时间复杂度是 \(O(N^2)\)，如果运用二分优化可以达到 \(O(nlogn)\) 。而本题的数据范围却能达到 \(10^6\)，不可能求LCS。
我们知道本题数组 \(A\) 可以无限拼接，因此，拼接后两个数组的最大LCS即为两个数组重复数字的个数。
为什么呢？
我们首先知道LCS的定义，它不要求数字连续出现，只是要求数字出现的顺序。而我们可以无限拼接，假设我们有长度为 \(n\) 的数组 \(A,B\)，满足 \(\forall A_i=B_{n-i}\)（假设这里 \(i\) 从0开始）。那么这两个数组拼接后能达到的最大LCS一定是 \(n\)，因为我们可以把数组 \(A\) 拼接 \(n\) 次。当然这是极端情况。类比地，无论两个数组的初始顺序如何，经过若干次拼接后的LCS一定是两个数组内数字重复的个数。即 \(\sum \limits_{i=1} ^ m [B_i \in A]\) （\(m\) 为 \(B\) 数组的大小）
在第一问，求LCS的时候，我们无需考虑重复的数字。因为 \(A\) 数组可以无限次拼接，只要出现了则一定可以满足。
再看第二问。
我们在处理的时候一定是由 \(B\) 去找 \(A\)。因为 \(B\) 数组的顺序是一定确定的。如果一个数字在 \(A,B\) 中同时出现。则一定属于LCS。那么什么时候需要拼接呢？一定是不满足在 \(B\) 中的顺序的时候。由于我们 \(B\) 是按顺序枚举的，所以也就是当前数字在 \(A\) 中的序号小于上一个数字在 \(B\) 中序号的时候。
这样的解决方案看似没有问题，如果一个数字在 \(A\) 中出现了多次呢？
很显然，由于求最小的拼接次数，我们一定要尽可能地使当前数字在 \(A\) 中的编号大于上一个数字在 \(A\) 中的编号。优先保证该条件。其次，当有多个编号满足时，我们一定贪心地选最小的。。因为这样下一位数字的编号满足条件1会更加容易，求得的\(k\)也就较小。贪心正确性显然。
具体实现的时候我们可以开一个 set <int> s[N];，每次操作 s[a[i]].insert(i)。同时存储一下 \(a_i\) 编号的最大值，输入的时候每次覆盖即可。这样后面判断是否需要 \(k++\) 的时候就好特判，显然如果最大的编号都要小于上次则肯定 \(k++\)，否则一定有解，upper_bound更新 \(pos\) 即可（\(pos\) 即为上一个数字在 \(A\) 中的编号)
作为基础赛T4，比较好想，实现的时候有简单有难，例如我们记录了 \(A\) 中的一个数字编号最大值，不仅在第二问处理方便，第一问也只需要判断这个值是不是为0即可。如果不记录这个值就会实现复杂。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int N = 1000010;
const int INF = 0x3f3f3f3f;
int n,m,c1,c2;
int s[N],t[N];
int vis[N];
int flg[N];
int maxn[N];
int k;
int lcs = 0;
vector <int> v[N];
set <int> st[N];
int pos = 0;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>c1>>c2;
for(int i=1;i<=n;i++)
{
cin>>s[i];
vis[s[i]] ++;
st[s[i]].insert(i);
maxn[s[i]] = i;
}
for(int i=1;i<=m;i++) cin>>t[i];
for(int i=1;i<=m;i++)
{
if(vis[t[i]])
{
lcs ++;
if(lcs == 1) k ++;
int minn = INF;
while(1)
{
if(maxn[t[i]] <= pos)
{
k ++;
pos = 0;
}
else
{
pos = *st[t[i]].upper_bound(pos);
break;
}
}
}
}
cout<<lcs*c1<<" "<<k*c2<<endl;
return 0;
}