本文主要是介绍CodeForces 337C Captains Mode(dp+位运算+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：CodeForces 337C Captains Mode
题目大意：dota2游戏选择英雄，先给出n个英雄的力量值，然后给出m个操作，p/b num，p代表第num个玩家可以选择一个英雄，b 代表第num个玩家可以封掉一个英雄，即谁都不可以选，然后两队选完之后，比较说两队英雄总力量值的差，两人都按照最优方案去选择。
解题思路：dp+位运算+贪心。首先选择英雄的时候，肯定是选择能量值最大的。其次m<= 20，也就是说不管是p还b，最多也就操作到20个英雄，所以将英雄按照力量值从大到小排序，选20个进行处理即可。
然后最多20个英雄，就可以用一个二进制数来表示，1表示不可选，0表示可选。碰到玩家1选择就加上能力值最大的英雄，玩家2选就剪掉能力值最大的英雄。如果碰到封除英雄，如果玩家1封，就要选策略中尽量大的，如果玩家2选，就要选择尽量小的。
#include <stdio.h>
#include <string.h>
#include <algorithm>using namespace std;const int N = (1 << 20) + 5;
const int M = 105;
const int INF = 0x3f3f3f3f;int n, m, v[N], h[M], order[M][2], rec[N];bool cmp(const int& a, const int& b) {return a > b;
}void init() {memset(v, 0, sizeof(v));char ch;scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &h[i]);sort(h, h + n, cmp);scanf("%d%*c", &m);for (int i = 0; i < m; i++) {scanf("%c %d%*c", &ch, &order[i][0]);order[i][1] = (ch == 'p' ? 1 : 0);}n = min(n, 20);
}int dp(int s, int d) {if (v[s]) return rec[s];if (d >= m) return 0;int& ans = rec[s]; v[s] = 1;ans = 0;while (d < m) {if (order[d][1]) {int id;for (id = 0; id < n; id++) if ((s & (1 << id)) == 0) break;s += (1 << id);order[d][0] == 1 ? ans += h[id] : ans -= h[id];} else {int tmp = order[d][0] == 1 ? -INF : INF;for (int i = 0; i < n; i++) if ((s & (1 << i)) == 0) {int t = dp(s + (1 << i), d+1);if (order[d][0] == 1) tmp = max(tmp, t);else tmp = min(tmp, t); }ans += tmp;break;}d++;}return ans;
}int main () {init();printf("%d\n", dp(0, 0));return 0;
}
这篇关于CodeForces 337C Captains Mode(dp+位运算+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
