Subsequences (easy version)

Created by LXC on Thu Oct 12 01:29:08 2023

https://codeforces.com/problemset/problem/1183/E

ranting: 2000

tag: dp, graphs, implementation, shortest paths

problem

给出一个长度为n的字符串s，你可以将s的子序列加入到一个无重集合S中，代价是s的长度-子序列的长度。

求让S恰好k个不同串的最小代价。

$0 < n,k \le 100$

solution

由于最多选取100个k。

可以直接广搜，优先将最长的子序列加入到S中。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    if (k == 1) {
        cout << "0\n";
        return;
    }
    set<string> st;
    queue<string> q;
    q.push(s);
    st.insert(s);
    int stp = 1;
    int ans = 0;
    while (q.size()) {
        int sz = q.size();
        for (int i=0; i<sz; i++) {
            string u = q.front();
            q.pop();
            int usz = u.size();
            for (int j=0; j<usz; j++) {
                string t = u.substr(0, j) + u.substr(j+1, usz-j-1);
                if (st.count(t)) continue; 
                st.insert(t);
                q.push(t);
                ans += stp;
                if (st.size() == k) {
                    cout << ans << "\n";
                    return ;
                }
            }
        }
        stp++;
    }
    cout << "-1\n";

}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}