CodeForces-Game with Marbles (Easy Version) 转存洛谷

LteShuai / 2024-08-05 / 原文

题目

题目分析

看到数据很小，( $ 2 \le n \le 6 $ )，考虑直接暴力深搜。

如果是甲所选，他会将 $a_i$ 减一且 $b_i$ 变为 $0$。
如果是乙所选，他会将 $b_i$ 减一且 $a_i$ 变为 $0$。
$A=\sum_{p=1}^{n}a_p\ , \ B=\sum_{p=1}^{n}b_p$。

甲想让 $A-B$ 越大越好，乙想让 $A-B$ 越小越好，如果甲乙足够聪明，那么最后 $A-B$ 的值为多少？

就是一个博弈论，双方所做的决策当前都是最优的才行，对于某一个时刻，说明下该操作的贡献，比如某刻甲来做决定，将 $b_i$ 变为 $0$，同时自身减一，所以贡献是 $a_i-1$。

题目思路

这道题的数据很小，但是在用深搜枚举的时候，并不是简简单单的一层一层往下搜索，因为这里是要满足双方两人的最优选法，所以这里的深搜写法应该是在搜同一层时找到当前最优解，使用该最优解去对前一层进行处理。

甲的先选，然后乙选，既然用搜索就不要考虑什么贪心了，直接开始搜，来个循环对甲的数组一个个遍历然后使用搜索，然后搜过的要用判重数组记录好，注意好回溯就行。

由于是博弈论，我们必须保证每一次搜索对于该阶段选的人最优，所以我们必须使用一个变量来记录当前最优值，所以需要使用 $\max$ 函数。

得到那个最优的答案，返回到上一层，就这样不断深搜到最后一层，找到了最优答案返回，一直返回到第一层，就这样就好了。

代码实现

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int vis[10];
int n;
struct node {
	ll x, y;
} ;
node a[10];
ll  LTE(int step) {
	if (step == n + 1)return 0;
	ll HS = -9e18 + 1;
	for (int i = 1; i <= n; i++) {
		if (vis[i])continue;
		if (step % 2 == 1) {
			vis[i] = 1;
			ll optimal=LTE(step+1);
			HS = max(HS, a[i].x - 1 - optimal);
			vis[i] = 0;
		} else {
			vis[i] = 1;
			ll optimal=LTE(step+1);
			HS = max(HS, a[i].y - 1 - optimal);
			vis[i] = 0;
		}
	}
	return HS;
}
int main() {
	int t;
	cin >> t;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while (t--) {
		memset(vis, 0, sizeof vis);
		memset(a, 0, sizeof a);
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> a[i].x;
		for (int i = 1; i <= n; i++)
			cin >> a[i].y;
		cout << LTE(1) << endl;
	}
	return 0;
}