Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- #include <algorithm>
- using namespace std;
- const int INF = 1e9;
- void solve() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- string heard_string;
- cin >> heard_string;
- map<char, int> char_to_index;
- int unique_char_count = 0;
- for (char c : heard_string) {
- if (char_to_index.find(c) == char_to_index.end()) {
- char_to_index[c] = unique_char_count++;
- }
- }
- const int N = unique_char_count;
- if (heard_string.empty()) {
- cout << 0 << "\n";
- return;
- }
- if (N <= 1) {
- cout << 1 << "\n";
- return;
- }
- vector<vector<int>> adjacency_counts(N, vector<int>(N, 0));
- for (size_t i = 0; i + 1 < heard_string.length(); ++i) {
- int u = char_to_index[heard_string[i]];
- int v = char_to_index[heard_string[i+1]];
- adjacency_counts[u][v]++;
- }
- vector<int> min_hums(1 << N, INF);
- min_hums[0] = 1;
- const int low_bits_count = N / 2;
- const int high_bits_count = N - low_bits_count;
- const int low_bits_mask = (1 << low_bits_count) - 1;
- vector<vector<int>> precomputed_sums_low(N, vector<int>(1 << low_bits_count, 0));
- vector<vector<int>> precomputed_sums_high(N, vector<int>(1 << high_bits_count, 0));
- for (int j = 0; j < N; ++j) {
- for (int mask = 1; mask < (1 << low_bits_count); ++mask) {
- int lsb_idx = __builtin_ctz(mask); // right most bit e.g. 10010 -> 00010
- int prev_mask = mask ^ (1 << lsb_idx);
- precomputed_sums_low[j][mask] = precomputed_sums_low[j][prev_mask] + adjacency_counts[j][lsb_idx];
- }
- for (int mask = 1; mask < (1 << high_bits_count); ++mask) {
- int lsb_idx = __builtin_ctz(mask); // right most bit e.g. 10010 -> 00010
- int prev_mask = mask ^ (1 << lsb_idx);
- precomputed_sums_high[j][mask] = precomputed_sums_high[j][prev_mask] + adjacency_counts[j][low_bits_count + lsb_idx];
- }
- }
- for (int mask = 1; mask < (1 << N); ++mask) {
- for (int j = 0; j < N; ++j) {
- if (mask & (1 << j)) {
- int prev_mask = mask ^ (1 << j);
- int current_total_cost = min_hums[prev_mask];
- int cost_of_adding_j = 0;
- int high_mask_part = mask >> low_bits_count;
- cost_of_adding_j += precomputed_sums_low[j][mask & low_bits_mask];
- cost_of_adding_j += precomputed_sums_high[j][high_mask_part];
- current_total_cost += cost_of_adding_j;
- min_hums[mask] = min(min_hums[mask], current_total_cost);
- }
- }
- }
- cout << min_hums[(1 << N) - 1] << "\n";
- }
- int main() {
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
