E - Ac Challenge 【18南京网络赛】

E - Ac Challenge

一个比较简单的 状压dp

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 21;

ll f[1 << N], a[N], b[N];
vector<int>G[N];
int n, m;
bool judge(int state, int pos) {
	// 判断state状态加入pos是否河里
	if (f[state] == -1 or (state & (1 << pos))) return false;
	for (int v : G[pos]) {
		if (not (state & (1 << v)))return false;
	}
	return true;
}
int count(int x) {
	int ans = 0;
	while (x)ans++, x -= (-x) & x;
	return ans;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld%lld%d", a + i, b + i, &m);
		while (m--) {
			int x; scanf("%d", &x);
			G[i].push_back(x-1);
		}
	}
	ll ans = 0;
	memset(f, 0xff, sizeof f);
	f[0] = 0;
	for (int i = 0; i < 1 << n; i++) {
		for (int j = 0; j < n; j++) {
			if (not judge(i, j))continue;
			f[i | (1 << j)] = max(f[i | (1 << j)], f[i] + (1 + count(i)) * a[j] + b[j]);
			ans = max(ans, f[i | (1 << j)]);
		}
	}
	printf("%lld\n", ans);
}

E - Ac Challenge 【18南京网络赛】

原文：https://www.cnblogs.com/sduwh/p/14070954.html