NOIP 2010 普及组 三国游戏

• 暴力搜索

#include 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 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，赢了*/