D

引领天下 · 2023-08-19 15:22:13 · 题解

前言：本题我读题读了 20min 没读懂，问学弟最长公共子序列需不需要连续花了 10min，最后过掉只花了 5min。

既然最长公共子序列不要求连续，那么考虑直接贪心地挨个处理 T 中的元素。

设当前我们已经使用了 k 次 S 串，第 k 次复制的 S 串已经用到了第 i 个位置，T 串已经处理到了第 j 个位置。

那么就分以下几种情况：

这个贪心策略的正确性的显然的，故此略去证明。

有了这个思路之后代码就很好实现了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,c1,c2,i,j,s[1000005],t[1000005],cnt=1,ansk;
vector<int>a[1000005];
signed 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],a[s[i]].push_back(i);
    for(int i=1;i<=m;i++)cin>>t[i];
    for(;j<=m;){
        bool flag=0;
        auto k=upper_bound(a[t[j]].begin(),a[t[j]].end(),i);//通过二分查找来找到第一个 l，注意因为我们是按顺序 push_back 的，所以 a[t[j]] 一定是升序的。
        if(k!=a[t[j]].end())i=*k,flag=1;
        else if(!a[t[j]].empty())i=*a[t[j]].begin(),cnt++,flag=1;
        if(flag)ansk++;
        j++;
    }
    cout<<c1*ansk<<' '<<c2*cnt;
    return 0;
}