题意：现在有n张卡片(n <= 16), 每一轮你可以执行两种操作中的一种。1：获得一张红色令牌和一张蓝色令牌。2：购买一张卡片（如果可以买的话），购买的时候蓝色卡片可以充当蓝色令牌，红色同理，但是购买后只消耗令牌，不消耗卡片。问最少多少轮可以购买全部卡片。
思路1：状压DP。我们发现卡片可以减少令牌的使用，如果不考虑卡片的话，总花费其实是固定的。所以，只要我们算出了通过令牌最多可以减免多少花费，就可以得到答案了。
设dp[i][j]为卡片的够买状态为i时，其中红色卡片的花费减免了j，蓝色卡片花费最多减免了多少，直接转移就可以了。求答案时，暴力枚举红色卡牌的减免来更新答案。
代码：
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int ans = 1e9, sum1, sum2, mx1, mx2;
char ch[10];
pii a[20];
int dp[1 << 16][260], sum[1 << 16][2], b[20];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s%d%d", ch, &a[i].first, &a[i].second);
sum1 += a[i].first, sum2 += a[i].second;
b[i] = (ch[0] == 'B');
}
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if((i >> j) & 1) {
if(b[j] == 0) sum[i][0]++;
else sum[i][1]++;
}
}
}
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < 240; j++) {
if(dp[i][j] == -1) continue;
for (int k = 0; k < n; k++) {
if((i >> k) & 1) continue;
int tmp3 = (i | (1 << k));
int tmp1 = min(sum[i][0], a[k].first), tmp2 = min(sum[i][1], a[k].second);
dp[tmp3][j + tmp1] = max(dp[tmp3][j + tmp1], dp[i][j] + tmp2);
}
}
}
int now = (1 << n) - 1;
for (int i = 0; i < 240; i++) {
if(dp[now][i] == -1) continue;
ans = min(ans, max(sum1 - i, sum2 - dp[now][i]) + n);
}
printf("%d\n", ans);
}
思路2：模拟退火。偶然发现300iq大神当年打这场比赛这题用的模拟退火，我们相当于是对购买的序列进行退火。要注意一点，随着退火的温度降低，活性也要降低，即随机的次数要降低，不能直接random_shuffle了事。
这次是真模拟退火，不是爬山，要跳出局部最优解。
代码：
#include <bits/stdc++.h>
#define db double
#define LL long long
using namespace std;
db T0 = 1000, eps = 1e-3;
int n;
mt19937 random(time(0));
struct node {
char ch;
int x, y;
node(char ch, int x, int y) : ch(ch), x(x), y(y) {}
node() {}
};
vector<node> a, b;
db get() {
LL x = random() + 1, y = random() + 1;
x %= y;
return (db) x / y;
}
int solve() {
int sum1 = 0, sum2 = 0, r = 0, b = 0, ans = 0;
for (int i = 0; i < n; i++) {
int cost = max(max(0, a[i].x - r - sum1), max(0, a[i].y - b - sum2));
sum1 = sum1 + cost - max(0, a[i].x - r);
sum2 = sum2 + cost - max(0, a[i].y - b);
ans += cost;
if(a[i].ch == 'R') r++;
else b++;
}
return ans + n;
}
int main() {
int x, y, ans = 1e9;
char ch[10];
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s%d%d", ch, &x, &y);
a.push_back(node{ch[0], x, y});
}
random_shuffle(a.begin(), a.end());
db temp = T0;
while(1) {
if(temp < eps) break;
int tmp = solve();
b = a;
//random_shuffle(a.begin(), a.end());
for (int i = 0; i < n * temp / T0; i++){
swap(a[random() % n], a[random() % n]);
}
int tmp1 = solve();
if(tmp1 < tmp) {
tmp = tmp1;
} else {
db change = exp(-(tmp1 - tmp) / temp);
if(get() > change) a = b;
else tmp = tmp1;
}
ans = min(ans, tmp);
temp *= 0.99999;
}
printf("%d\n", ans);
}