大家好！我是小码匠。
今天分享的题目是状压DP题，这道题最大槽点：难度标签不太对，状压DP一般都要【普及/提高-】起。
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：9道
- 待完成：291道
已完成目标：
分类 | 算法 | 题目 |
|---|---|---|
算法基础 | 前缀和 | 【第001题】题解分享：湖南省选->激光炸弹 |
算法基础 | 差分 | 【第002题】题解分享：P4552 [Poetize6] IncDec Sequence |
算法基础 | 高维前缀和 | 【第003题】题解及代码分享：CodeForces 165E Compatible Numbers |
算法基础 | 尺取 | 【第004题】题解及代码分享：AtCoder ABC326-C |
动态规划 | 动态规划 | 【第005题】题解及代码分享：AtCoder ABC326-D |
算法基础 | 高维前缀和 | 【第006题】题解及代码分享：高位前缀和之AtCoder ARC100 - E Or Plus Max |
动态规划 | 数位DP | 【第007题】题解及代码分享：数位DP经典模版题 [SCOI2009] windy 数 |
动态规划 | 数位DP | 【第008题】题解及代码分享：数位DP[ZJOI2010] 数字计数 |
前置知识
- 状压 DP
- https://oi-wiki.org/dp/state/
题目描述
数据有n组数,每组数有一个价值
和一个字符串S,字符串S中包含3个字母A,B,C，问集齐ABC三个字母的最小价值（一个字母可以有多个）
输入输出样例
输入 #1
代码语言：javascript复制4
5 C
6 B
16 BAC
4 A
输出 #1
代码语言：javascript复制15
输入 #2
代码语言：javascript复制2
10 AB
15 BA
输出 #2
代码语言：javascript复制-1
输入 #3
代码语言：javascript复制5
10 A
9 BC
11 CA
4 A
5 B
输出 #3
代码语言：javascript复制13
输入 #4
代码语言：javascript复制6
100 A
355 BCA
150 BC
160 AC
180 B
190 CA
输出 #4
代码语言：javascript复制250
输入 #5
代码语言：javascript复制2
5 BA
11 CB
输出 #5
代码语言：javascript复制16
题解
AC代码
代码语言：javascript复制#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;
}END
