[CF1183E] Subsequences (easy version)

[CF1183E] Subsequences (easy version) - BFS

Description

给你一个长度为 (n(nle 100)) 的字符串，找出其中 (k(k le 100)) 个不同子序列（可不连续），使得代价（删除字符数）最小。

Solution

考虑 BFS，用 map 去重，每次枚举删除哪个字符，这样复杂度在 (O(nk^2))

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

#define int long long

int n, m;
map<string, int> mp;

signed main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    string str;
    cin >> str;

    queue<string> que;
    que.push(str);

    int ans = 0;

    while (que.size() && m)
    {
        string s = que.front();
        que.pop();

        if (mp[s])
            continue;
        mp[s] = 1;
        m--;
        ans += n - s.length();
        if (m == 0)
        {
            cout << ans << endl;
            return 0;
        }

        for (int i = 0; i < s.length(); i++)
        {
            string t = s;
            t.erase(t.begin() + i);

            que.push(t);
        }
    }

    cout << -1 << endl;
}