P1199 三国游戏

作者

[永遠の記憶 ~ Precious Memories]施工D7

2020.3.13

转载自luogu

P1199 三国游戏

Noip2010 T4

题目传送门

这是一道贪心+博弈论的题
关于这种题目，我们要明白一件事情:

人类是不可能输给计算机的

翻译成正常语言就是:

输出第一行只要无脑输出1就好了

然后我们仔细观察题意就会发现，
计算机是用贪心的方法在选将
也就是说计算机每次会选出默契值最大的那一组
当最大一组被选掉时，作为小涵，
我们的最优方案就是去选第二大的那一组

综上，我们可以写出最后的代码:

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

typedef long long ll;
const int maxn = 505;
ll num[maxn][maxn];
ll n;
ll x;
ll m1, m2;
ll ans = -1e7;

int main() {
	memset(num, false, sizeof(num));
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		m1 = 0;
		m2 = 0;
		for (int j = i + 1; j <= n; ++j) {
			cin >> x;
			num[i][j] = x;
			num[j][i] = x;
		}
		for (int j = 1; j <= n; ++j) {
			if (num[i][j] > m1) {
				m2 = m1;
				m1 = num[i][j];
			}
			else if (num[i][j] > m2) {
				m2 = num[i][j];
			}
		}
		ans = max(ans, m2);
	}
	printf("1\n%lld\n", ans);
	return 0;
}

这道题很玄，做出来主要是凭感觉。。。

发表评论