HDU-6435

2022-04-25

字数统计: 912字 | 阅读时长≈ 4分

题目大意

给定\(n\)种主武器和\(m\)把种武器，每种武器都有一个攻击力\(S\)和\(k\)种副属性\(a_i\)。选择一种主武器和一种副武器，使得 \[S_m + S_s + \sum |a_m[i] - a_s[i]|\]最大化。题目链接

思路

\(\sum |a_m[i] - a_s[i]|\)这个东西，其实就是高纬度的曼哈顿距离。二维曼哈顿距离是我们最常见的\(|x1 - x2| + |y1 + y2|\) 如果我们把曼哈顿距离同属性的放到一块，再去掉绝对值，就会变成形如\((-x1 + y1) + (x1 - y1)\)，二维的话，就有\(4\)种情况，\(k\)维的话就有\(2^k\)种形式。

我们单独把每个武器的副属性给展开成这种\(2^k\)种形式，用\(01\)二进制表示每个属性是\(+\)还是\(-\),把它们全部相加，并且把攻击力加上，记为\(S_m[i][j]\),即第\(i\)把主武器,展开形式为\(j\)。

\(k'\)就是\(k\)按位取反(对应到每个属性就是正负相反)

那么\(max(S_m + S_s + \sum |a_m[i] - a_s[i]|) = max(S_m[i][k] + S_s[j][k']), i \in[1,n], j \in [1.m]\) 然而，遍历这个式子的时间复杂度是\(O(nmk)\)，所以我们想办法化简这个式子。

考虑一个简单的问题: 设有两个数组\(a_n,b_m\),求\(max(a[i] + b[j]),i \in[1,n], j \in [1.m]\)。

直接硬算需要两重循环

注意到 \(a[i] + b[j]\)这个组合遍历到了所有\(a[i],a[j]\)的组合，即任意指定的\(i,j\),\(a[i],a[j]\)都会被遍历到。

而\(max(a[i] + b[j]) \le max(a[i]) + max(b[j])\), 而\(max(a[i]) + max(b[j])\)这个值也一定能被遍历到，所以就有 \[max(a[i] + b[j]) = max(a[i]) + max(b[j])\]

那么这么算就从两重循环变成了两个循环。

对应到这个题目中，\(max(S_m[i][k] + S_s[j][k']), i \in[1,n], j \in [1.m]\),实际上也遍历到了所有组合(注意合法组合一定比不合法的大，比如|5 - 2|的合法组合是\(+5,-2\),那么它就比不合法组合\(-5,+2\)要大)。

所以上面式子也可以继续化简: \(max(S_m[i][k] + S_s[j][k']) = max(S_m[i][k]) + max(s_s[j][k'])\)

而对于每个\(k\)，我们只需要得到它的最大值，所以\(i\)这一维也可以省去,我们\(S_m[k] = max(S_m[i][k])\) 那么上式子可以再度化简为: \[max(S_m[k] + S_s[k'])\]

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int T, n, m, k, s[8], x;

const long long INF = 0x7f7f7f7f;

long long s1[1 <<11], s2[1 << 11];

int main()
{
    scanf("%d", &T);
    while(T--) {
        for(int i = 0; i < 1 << 11; ++i)
            s1[i] = s2[i] = -INF;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &x);
            for(int j = 1; j <= k; ++j)
                scanf("%d", &s[j]);
            for(int j = 0; j < 1 << k; ++j) {
                long long sum = x;
                for(int l = 1; l <= k; ++l) {
                    if((j >> (l - 1)) & 1)
                        sum += s[l];
                    else
                        sum -= s[l];
                }
                s1[j] = max(s1[j], sum);
            }
        }
        for(int i = 1; i <= m; ++i) {
            scanf("%d", &x);
            for(int j = 1; j <= k; ++j)
                scanf("%d", &s[j]);
            for(int j = 0; j < 1 << k; ++j) {
                long long sum = x;
                for(int l = 1; l <= k; ++l) {
                    if((j >> (l - 1)) & 1)
                        sum -= s[l]; //这里我直接反着存，相当于直接取反了
                    else
                        sum += s[l];
                }
                s2[j] = max(s2[j], sum);
            }
        }
        long long ans = 0;
        for(int i = 0; i <= 1 << k; ++i)
            ans = max(ans, s1[i] + s2[i]);
        printf("%lld\n", ans);
    }
    return 0;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2022/04/25/HDU-6435/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！