题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6435
Solution
看了题解才明白，记录一下现在的理解。
我们需要求n个主武器和m个副武器之间各取一个的曼哈顿最大距离和
考虑每一个维度只有+-两种情况，那么k维就有2^k种（每一个武器都有2^k种），那么总的就是2^k(n+m)种情况，也就是最后的时间复杂度啦
（第一个数直接+，不放进枚举里面）
我们考虑最终答案就是M的加加减减组合与S的减减加加（主武器和副武器相反）
假设此时当前枚举产生最终答案，即最大值，此时的M集合最大值为m,S集合求出的相反最大值为s，则m+s为最大值（最终答案）
我们用反证法来证明
当前枚举产生最终答案，如果m+s不是最大值，则必有m’>m或n’>n存在于M，S集合，这与前提矛盾，原命题得证
而一共2^k的枚举中，必有一个枚举产生答案，因此这样一定能找到最终的最大值
1 /* 2 曼哈顿最大距离和 3 考虑每一个维度只有+-两种情况 4 2进制枚举(1<<k)种，主武器和副武器是+-刚好相反 5 O(2^k(m+n))取最大值 6 */ 7 #include <bits/stdc++.h> 8 #define lson rt << 1, l, mid 9 #define rson rt << 1 | 1, mid + 1, r 10 using namespace std; 11 using ll = long long; 12 using ull = unsigned long long; 13 using pa = pair<int, int>; 14 using ld = long double; 15 int n, m, k; 16 const int maxn = 1e5 + 10; 17 const int inf = 0x3f3f3f3f; 18 template <class T> 19 inline T read(T &ret) 20 { 21 int f = 1; 22 ret = 0; 23 char ch = getchar(); 24 while (!isdigit(ch)) 25 { 26 if (ch == '-') 27 f = -1; 28 ch = getchar(); 29 } 30 while (isdigit(ch)) 31 { 32 ret = (ret << 1) + (ret << 3) + ch - '0'; 33 ch = getchar(); 34 } 35 ret *= f; 36 return ret; 37 } 38 template <class T> 39 inline void write(T n) 40 { 41 if (n < 0) 42 { 43 putchar('-'); 44 n = -n; 45 } 46 if (n >= 10) 47 { 48 write(n / 10); 49 } 50 putchar(n % 10 + '0'); 51 } 52 struct node 53 { 54 int s; 55 vector<int> sub; 56 }; 57 vector<node> M, S; 58 int main(int argc, char const *argv[]) 59 { 60 #ifndef ONLINE_JUDGE 61 freopen("in.txt", "r", stdin); 62 freopen("out.txt", "w", stdout); 63 #endif 64 int t; 65 read(t); 66 while (t--) 67 { 68 M.clear(), S.clear(); 69 read(n), read(m), read(k); 70 for (int i = 0; i < n; i++) 71 { 72 node now; 73 read(now.s); 74 for (int j = 0; j < k; j++) 75 { 76 int p; 77 read(p); 78 now.sub.emplace_back(p); 79 } 80 M.emplace_back(now); 81 } 82 for (int i = 0; i < m; i++) 83 { 84 node now; 85 read(now.s); 86 for (int j = 0; j < k; j++) 87 { 88 int p; 89 read(p); 90 now.sub.emplace_back(p); 91 } 92 S.emplace_back(now); 93 } 94 int l = (1 << k); 95 ll ans = -inf; 96 for (int i = 0; i < l; i++) 97 { 98 ll t1 = -inf, t2 = -inf; 99 for (int j = 0; j < n; j++) 100 { 101 ll tmp = M[j].s; 102 for (int p = 0; p < k; p++) 103 if ((i >> p) & 1) 104 tmp += M[j].sub[p]; 105 else 106 tmp -= M[j].sub[p]; 107 t1 = max(tmp, t1); 108 } 109 for (int j = 0; j < m; j++) 110 { 111 ll tmp = S[j].s; 112 for (int p = 0; p < k; p++) 113 if ((i >> p) & 1) 114 tmp -= S[j].sub[p]; 115 else 116 tmp += S[j].sub[p]; 117 t2 = max(tmp, t2); 118 } 119 ans = max(ans, t1 + t2); 120 } 121 write(ans); 122 puts(""); 123 } 124 return 0; 125 }
View Code