hdu 6435 Problem J. CSGO 最长曼哈顿距离+二进制枚举

题目链接: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