A1000 全站本题第一个题解

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>


const int INF = 1e9;
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::string heard;
    std::cin >> heard;
    if (heard.empty()) {
        std::cout << 0 << "\n";
        return 0;
    }
    if (heard.size() == 1) {
        std::cout << 1 << "\n";
        return 0;
    }
    std::map<char, int> index;
    int n = 0;
    for (char letter : heard) {
        if (index.find(letter) == index.end()) {
            index[letter] = n++;
        }
    }
    std::vector<std::vector<int>> adjacent(n, std::vector<int>(n, 0));
    for (size_t j = 1; j < heard.size(); ++j) {
        ++adjacent[index[heard[j - 1]]][index[heard[j]]];
    }
    std::vector<long long> dp(1 << n, INF);
    dp[0] = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                int prev_mask = mask ^ (1 << i);
                long long cost_to_add = 0;
                for (int j = 0; j < n; ++j) {
                    if (prev_mask & (1 << j)) {
                        cost_to_add += adjacent[i][j];
                    }
                }
                cost_to_add += adjacent[i][i];
                if (dp[prev_mask] != INF) {
                    dp[mask] = std::min(dp[mask], dp[prev_mask] + cost_to_add);
                }
            }
        }
    }
    std::cout << dp[(1 << n) - 1] + 1 << "\n";
    return 0;
}