1 条题解
-
1
#include <bits/stdc++.h> using namespace std; const int MAX_N = 30; const int inf = INT_MAX / 3; int n, a[MAX_N], b[MAX_N], t[MAX_N], ans = inf; int que_a[MAX_N], que_b[MAX_N], top_a, top_b; bool flag[MAX_N]; int read() { int x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } bool cmp_a(int x, int y) { return b[x] == b[y] ? a[x] < a[y] : b[x] > b[y]; } bool cmp_b(int x, int y) { return a[x] == a[y] ? b[x] < b[y] : a[x] > a[y]; } int calc() { int sum_a = 0, sum_b = 0, re = 0; for (int i = 1; i <= top_a; i++) sum_a += a[que_a[i]]; for (int i = 1; i <= top_b; i++) { sum_b += b[que_b[i]]; if (sum_a > sum_b) sum_a += a[que_b[i]]; else sum_a = sum_b + a[que_b[i]]; } re = max(sum_a, sum_b); sum_a = sum_b = 0; for (int i = 1; i <= top_b; i++) sum_b += b[que_b[i]]; for (int i = 1; i <= top_a; i++) { sum_a += a[que_a[i]]; if (sum_b > sum_a) sum_b += b[que_a[i]]; else sum_b = sum_a + b[que_a[i]]; } return max(re, max(sum_a, sum_b)); } void solve() { top_a = top_b = 0; for (int i = 1; i <= n; i++) if (flag[i]) que_b[++top_b] = i; else que_a[++top_a] = i; sort(que_a + 1, que_a + top_a + 1, cmp_a); sort(que_b + 1, que_b + top_b + 1, cmp_b); int re = calc(); for (int cas = 1; cas <= 2000; cas++) { int a1, a2, b1, b2, tmp; if (top_a) swap(que_a[a1 = (rand() % top_a) + 1], que_a[a2 = (rand() % top_a) + 1]); if (top_b) swap(que_b[b1 = (rand() % top_b) + 1], que_b[b2 = (rand() % top_b) + 1]); tmp = calc(); if (tmp < re) re = tmp; else { if (top_a) swap(que_a[a1], que_a[a2]); if (top_b) swap(que_b[b1], que_b[b2]); } } if (re < ans) ans = re; } void dfs(int dep) { if (dep > n) solve(); else if (t[dep] == 1) flag[dep] = 0, dfs(dep + 1); else if (t[dep] == 2) flag[dep] = 1, dfs(dep + 1); else { flag[dep] = 0; dfs(dep + 1); flag[dep] = 1; dfs(dep + 1); } } int main() { srand(time(NULL) + 19260817); n = read(); for (int i = 1; i <= n; i++) t[i] = read(), a[i] = read(), b[i] = read(); dfs(1); printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 2336
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 6
- 已通过
- 2
- 上传者