题目描述

blablabla

这代码是我五个月前写的，而且ac了，真不知道我那时是怎么想到的，我感觉我现在真不如那个时候

样例

#include <bits/stdc++.h>

using namespace std;

const int N = 5010;

unordered_map<string, int> mm; // 记录该字符上一次出现的位置
set<string> st;

int q[N];

int main()
{
    int n, m;

    cin >> n;

    string s;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> s;
        mm[s] = 0;
        st.insert(s);
    }

    cin >> m;



    for (int i = 1; i <= m; i ++ )
    {
        cin >> s;



        if(st.count(s))
        {
            mm[s] = i;
            int minpay = 9e8;
            for (auto it = mm.begin(); it != mm.end(); ++ it)
            {
                if (it->first != s)
                {
                    minpay = min(minpay, q[it->second] + 1);
                }
            }

            if (minpay == 9e8)
            {
                cout << -1 << endl;
                return 0;
            }

            q[i] = minpay;

        }
    }
    /*
    for (int i = 1; i <= m; i ++ )
    {
        cout << q[i] << " ";
    }
    cout << endl;
    */
    int minitime = 9e8;

    for (auto it = mm.begin(); it != mm.end(); ++it)
    {
        //cout << it->second << endl;
        minitime = min(minitime, q[it->second]);
    }


    cout << minitime << endl;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla