Leave a Comment
给出1~9数字的个数,求最多能构成多少个不同的等式,x + y = z,x、y、z都是一位数字,1 + 2 = 3 和 2 + 1 = 3算不同的式子。
对于1 + 2,1 + 3 … 1 + 8,这些式子可以贪心的取,能取的就取,那么剩下的式子有18个x != y的式子,4个x == y的式子,对于x != y的式子可以考虑将1 + 2 和 2 + 1这样的式子一起考虑,那么就是3 ^ 9 * 2 ^ 4,加上贪心的judge,那么总复杂度是O(3 ^ 9 * 2 ^ 4 * 9 * T)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; int num[10], tmp[10], x[30], y[30], z[30], sz; int ans; void init(){ sz = 0; for(int i = 2; i <= 9; i++){ for(int j = i + 1; i + j <= 9; j++){ x[sz] = i; y[sz] = j; z[sz++] = i + j; } } for(int i = 1; i <= 4; i++){ x[sz] = i; y[sz] = i; z[sz++] = 2 * i; } } bool judge(int a[], int x, int y, int z, int t){ if(x == y) return a[x] >= 2 * t && a[z] >= t; return a[x] >= t && a[y] >= t && a[z] >= t; } int cal(){ for(int i = 1; i <= 9; i++) tmp[i] = num[i]; int ans = 0; for(int i = 2; i < 9 && tmp[1]; i++){ int t = min(2, min(tmp[1], min(tmp[i], tmp[i + 1]))); if(t && judge(tmp, 1, i, i + 1, t)){ tmp[1] -= t; tmp[i] -= t; tmp[i + 1] -= t; ans += t; } } return ans; } void dfs(int idx, int cnt){ ans = max(ans, cnt + cal()); if(idx == sz) return; dfs(idx + 1, cnt); int up = x[idx] != y[idx] ? 2 : 1; for(int i = 1; i <= up; i++){ if(judge(num, x[idx], y[idx], z[idx], i)){ num[x[idx]] -= i; num[y[idx]] -= i; num[z[idx]] -= i; dfs(idx + 1, cnt + i); num[x[idx]] += i; num[y[idx]] += i; num[z[idx]] += i; } } } int main(){ init(); int T; scanf("%d", &T); for(int cas = 1; cas <= T; cas++){ for(int i = 1; i <= 9; i++){ scanf("%d", &num[i]); } ans = 0; dfs(0, 0); printf("Case #%d: %d\n", cas, ans); } return 0; } /* 5 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0 3 3 0 3 0 0 0 0 100 100 100 100 100 100 100 100 1 100 100 100 100 100 100 100 100 100 10 16 15 14 13 12 11 10 9 8 15 15 14 13 12 11 10 9 8 16 14 14 13 12 11 10 9 8 16 15 13 13 12 11 10 9 8 16 15 14 12 12 11 10 9 8 16 15 14 13 11 11 10 9 8 16 15 14 13 12 10 10 9 8 16 15 14 13 12 11 9 9 8 16 15 14 13 12 11 10 8 8 16 15 14 13 12 11 10 9 7 1 15 14 13 12 11 10 9 8 7 1 15 15 14 13 12 11 10 9 8 */ |