【第009题】题解及代码分享：【难度】标签有毒，状压DP，CF1042B-Vitamins

4
5 C
6 B
16 BAC
4 A

15

2
10 AB
15 BA

-1

5
10 A
9 BC
11 CA
4 A
5 B

13

6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA

250

2
5 BA
11 CB

16

#include <bits/stdc++.h>

using namespace std;

int dp[1 << 3], num[1005], w[1005];
const int INF = 0x3f3f3f3f;

void best_coder() {
    memset(dp, INF, sizeof(dp));
    int n;
    cin >> n;
    int l = 0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> w[i + 1] >> s;
        int t = 0;
        for (int j = 0; j < s.size(); ++j) {
            t = t | (1 << (s[j] - 'A'));
        }
        num[++l] = t;
    }

    dp[0] = 0;
    for (int j = 1; j <= n; ++j) {
        for (int i = (1 << 3) - 1; i >= 0; --i) {
            dp[i | num[j]] = min(dp[i | num[j]], dp[i] + w[j]);
        }
    }
    if (dp[(1 << 3) - 1] == INF) {
        cout << -1;
    } else {
        cout << dp[(1 << 3) - 1];
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}