[数据结构与算法]NOIP 2010 普及组 三国游戏

• 暴力搜索

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

const int N = 510;
int n, w[N][N];			//武将的默契值
int a[N/2], b[N/2];		//小涵和计算机的武将序号 
bool chosen[N];			//武将是否被挑选出来
int ans;				//最大默契值 

//当前挑选小涵的第x个武将 
void dfs(int x) {
	if (x > n/2) {
		int w1 = 0, w2 = 0;
		//枚举小涵的武将中默契值最高的一堆 
		for (int i = 1; i <= n/2; i ++) {
			for (int j = i + 1; j <= n/2; j ++) {
				w1 = max(w1, w[a[i]][a[j]]);
			}
		}
		//枚举计算机的武将中默契值最高的一堆
		for (int i = 1; i <= n/2; i ++) {
			for (int j = i + 1; j <= n/2; j ++) {
				w2 = max(w2, w[b[i]][b[j]]);
			}
		}
		if (w1 > w2) ans = max(ans, w1);
		return;
	}
	
	for (int i = 1; i <= n; i ++) {
		if (!chosen[i]) {
			a[x] = i;			//如果第i个武将是自由的，被小涵挑出 
			chosen[i] = true;	

			int t = 0;
			for (int j = 1; j <= x; j ++) {
				for (int k = 1; k <= n; k ++) {
					//计算机的挑选策略
					if (!chosen[k] && w[a[j]][k] > w[a[j]][t]) {
						t = k;	 
					}
				}
			}
			
			b[x] = t;
			chosen[t] = true;
			dfs(x + 1);
			chosen[i] = false;
			chosen[t] = false;
		}
	}	
}

int main() {
	cin >> n;
	for (int i = 1; i < n; i ++) {
		for (int j = 1; j <= n - i; j ++) {
			int t;
			cin >> t;
			w[i][i+j] = w[i+j][i] = t;
		}
	}

	dfs(1);
	
	if (ans == 0) cout << 0 << endl;
	else cout << 1 << endl << ans << endl;

	return 0;
}

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

int n, m;
struct info {
	int x, y, w;
}a[260000];

bool cmp (info s, info t) { return s.w > t.w; }

int main() {
	cin >> n;
	for (int i = 1; i < n; i ++) {
		for (int j = 1; j <= n - i; j ++) {
			int t;
			cin >> t;
			a[++ m] = (info) {i, i + j, t};
		}
	}
	sort(a + 1, a + 1 + m, cmp);
	
	set <int> s;
	for (int i = 1; i <= m; i ++) {
		int x = a[i].x, y = a[i].y, w = a[i].w;
		if (s.count(x) || s.count(y)) {
			cout << 1 << endl << w;
			return 0;
		}
		else {
			s.insert(x);
			s.insert(y);
		}		
	}
	cout << 0;

	return 0;
}

/*
如果，
x和y的武力值第一大
x和z的武力值第二大
那么我方先取x，对方一定取y，我方再取z，赢了

如果，
a和b的武力值第一大
x和y的武力值第二大 
c和d的武力值第三大 
x和z的武力值第四大
那么我方先取x，对方一定取y，我方再取z，赢了

如果，
a和b的武力值第一大 
c和d的武力值第二大 
......
x和y的武力值第?大
......
x和z的武力值第??大 
那么我方先取x，对方一定取y，我方再取z，赢了
*/