GYM 101933E 状态压缩 + 记忆化搜索

题意：我方有n个士兵，敌方有m个，每方士兵都有一个血量，现在有k轮无差别炮火打击，每次都会从存活的士兵中随机选一人，这名士兵的HP就-1,问对方被团灭的概率有多大？

思路：因为n和m的范围很小，我们可以考虑暴力搜索，中间使用记忆化。这里状态压缩有一个小技巧，我们的正常想法是：因为士兵总数最多只有10个，我们可以用一个十位数来表示状态，每一位数代表这个士兵的现在的HP。但是我这样设计状态超时了。。。网上的状态设置的比较巧妙，网上用了12位数来表示状态，每一位代表敌方或者我方的HP为某个值的士兵还剩多少个。这样设计状态的好处在于如果有多个士兵的HP相同，那么只需向下搜索一个就行了，大大减少了搜索的分支。

代码：

#include <bits/stdc++.h>

#define LL long long

#define db double

using namespace std;

map<LL, db> dp;

int now_state[2][7];

int n, m;

LL limit;

LL get_state(void) {

	LL state = 0;

	for (int i = 1; i <= 6; i++)

		state = state * 10 + now_state[1][i];

	for (int i = 1; i <= 6; i++)

		state = state * 10 + now_state[0][i];

	return state;

}

db dfs(LL state, int deep) {

	if(dp.count(state)) return dp[state];

	if(state < 1000000) return 1;

	if(deep == 0) return 0;

	int cnt = 0;

	db ans = 0;

	for (int i = 0; i <= 1; i++)

		for (int j = 1; j <= 6; j++)

			cnt += now_state[i][j];

	for (int i = 0 ; i <= 1; i++)

		for (int j = 1; j <= 6; j++) {

			if(!now_state[i][j]) continue;

			now_state[i][j]--;

			now_state[i][j - 1]++;

			ans += dfs(get_state(), deep - 1) * (now_state[i][j] + 1) / (db) cnt;

			now_state[i][j]++;

			now_state[i][j - 1]--;

		}

	dp[state] = ans;

	return ans;

}

int main() {

	int k, x;

	scanf("%d%d%d", &n, &m, &k);

	for (int i = 1; i <= n; i++) {

		scanf("%d", &x);

		now_state[0][x]++;

	}

	for (int i = 1; i <= m; i++) {

		scanf("%d", &x);

		now_state[1][x]++;

	}

	printf("%.7lf\n", dfs(get_state(), k));

}

巴特西

GYM 101933E 状态压缩 + 记忆化搜索

最新文章

热门文章