[hdu6435]Problem J. CSGO

题目大意：给定$n$个$A$类元素和$m$个$B$类元素，每类元素有值$S$和$k$个值$x_0,x_1,\dots,x_{k-1}(k\leqslant 5)$。

要求选出一个$A$类元素$a$和$B$类元素$b$，最大化$a.S+b.S+\sum\limits_{i=0}^{k-1}|a.x_i-b.x_i|$。

题解：发现$k\leqslant 5$，可以搞事情，$|a-b|=max(a-b,b-a)$，枚举每个元素的$x_i$是正是负，对每个一个状态求出在$A$和$B$中的最大值，取最大值就行了

卡点：无

C++ Code：

#include <cstdio>

#include <cstring>

#define maxn 100010

const long long inf = 0x3f3f3f3f3f3f3f3f;

int Tim;

int n, m, K, U;

long long MW[1 << 5 | 3], SW[1 << 5 | 3], x[10];

long long ans;

inline long long max(long long a, long long b) {return a > b ? a : b;}

void read(int n, long long *W) {

	long long tmp;

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

		scanf("%lld", &tmp);

		for (int j = 0; j < K; j++) scanf("%lld", x + j);

		for (int j = 0; j < U; j++) {

			long long tmp6 = tmp;

			for (int k = 0; k < K; k++) tmp6 += (j & (1 << k)) ? x[k] : -x[k];

			W[j] = max(W[j], tmp6);

		}

	}

}

int main() {

	scanf("%d", &Tim);

	while (Tim --> 0) {

		scanf("%d%d%d", &n, &m, &K); ans = -inf;

		U = 1 << K;

		for (int i = 0; i < U; i++) MW[i] = SW[i] = -inf;

		read(n, MW);

		read(m, SW);

		for (int i = 0; i < U; i++) {

			ans = max(ans, MW[i] + SW[(U - 1) ^ i]);

		}

		printf("%lld\n", ans);

	}

	return 0;

}

巴特西

[hdu6435]Problem J. CSGO

最新文章

热门文章