Codeforces 745E Hongcow Buys a Deck of Cards 状压DP / 模拟退火

题意：现在有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);

}

巴特西

Codeforces 745E Hongcow Buys a Deck of Cards 状压DP / 模拟退火

最新文章

热门文章