P9572 Colorful Days♪　题解

Jorisy · 2023-08-19 19:06:12 · 题解

赛时口胡的竟然过了。

首先考虑到，在 S 中没出现的 T_i 必然不会对 \operatorname{LCS}(S^k,T) 产生贡献。因此直接删去变成新的 T'。显然，\max\{\operatorname{LCS}(S^k,T')\}=|T'|。第一问做完了。

然后转向第二问。

考虑记录 T 的每个数 T_i 在 S 中出现的位置，然后我们将 T_i 映射到 T_i 在 S 中的编号 P_i。这里我们为了 k 尽可能小，就要尽可能使得 P_i>P_{i-1}(i>1) 且 P_i 尽可能小。如果不行，那我们只能开启新的 S（即 k 加一）再次贪心。

时间复杂度 O(m\log n)。

#include<bits/stdc++.h>
using namespace std;

vector<int>v[1000005];
int n,m,p,c1,c2,a[1000005],b[1000005],ans;

int main()
{
    scanf("%d%d%d%d",&n,&m,&c1,&c2);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);//记录每个数对应的所有编号
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i]);
        if(v[b[i]].size()) b[++p]=b[i];
    }
    m=p;
    printf("%d ",p*c1);
    int lst=0;
    for(int i=1;i<=m;i++)
    {
        auto t=lower_bound(v[b[i]].begin(),v[b[i]].end(),lst+1);//贪心选择比其大的当中编号尽可能小的
        if(t==v[b[i]].end())//找不到
        {
            ans++;
            lst=*v[b[i]].begin();
        }
        else lst=*t;
    }
    cout<<++ans*c2;
    return 0;
}

P9572 Colorful Days♪ 题解

P9572 Colorful Days♪　题解