P9572

TanX_1e36 · 2023-08-19 19:45:15 · 题解

题目大意：

有两个数组 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(n\log n+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;
}