洛谷---CF1042B Vitamins---状压DFS(剪枝)

输入输出样例

输入 #1

4
5 C
6 B
16 BAC
4 A

输出 #1

15

输入 #2

2
10 AB
15 BA

输出 #2

-1

输入 #3

5
10 A
9 BC
11 CA
4 A
5 B

输出 #3

13

输入 #4

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

输出 #4

250

输入 #5

2
5 BA
11 CB

输出 #5

16

代码

#include <iostream>
#include <string>
#include <cstring>
#include <vector>using namespace std;const int MAX_N = 1e3 + 3;
const int inf = 0x3f3f3f3f;
pair<int, string> v[MAX_N];
int a[1 << 3], n;void dfs(int index, int pre)
{// 超出数组范围，退出dfsif (index == n)return;// 不选择当前数，快进到选择下一个数dfs(index + 1, pre);// 记录now的初始值是前一个传过来的状态int now = pre;// 用当前的index对应的字符串修改状态for (char c : v[index].second){now |= 1 << (c - 'A');}// 若此状态不够优则退出搜索，剪枝if (a[now] < a[pre] + v[index].first)return;// 若更优则修改新状态并继续搜索a[now] = a[pre] + v[index].first;dfs(index + 1, now);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(a, inf, sizeof a);cin >> n;for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;a[0] = 0;dfs(0, 0);cout << (a[7] == inf ? -1 : a[7])<< endl;return 0;
}