HDU 6435 Problem J.CSGO【思维】【二进制枚举】

发表于 | 更新于 | 分类于

题目大意：

现在有n把主武器和m把副武器，每个武器除了有1个固定属性外，还有k个能互相影响的属性，具体体现在当你选择两把武器时，固定属性带给你的加成是两者的固定属性值之和，而这k个属性带给你的加成是两武器的对应各属性差的绝对值之和。

现在要你选择一把主武器和一把副武器，使得两武器配合带来的加成最大。

解题思路：

考虑到n和m的范围最大值都是100000，所以直接看搭配方案是不可行的，而属性k最大只有5，我们可以从这里入手。两武器搭配，对应的k个属性要么是加上带来的加成，要么是减去带来的加成，所以我们可以把每一把武器的每一种状态都枚举出来，就是$2^k$种加减组合，枚举的同时更新此状态下的最大值，对于最后的答案就是将主武器的这个集合和副武器的补集求和。

Mycode：

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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;

int t, n, m, k, up;
ll v, a[6], MW[44], SW[44];
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        up = 1 << k;
        memset(MW, -INF, sizeof(MW));
        memset(SW, -INF, sizeof(SW));

        for(int o = 0; o < n; ++o)
        {
            scanf("%lld", &v);
            for(int i = 0; i < k; ++i)
                scanf("%lld", &a[i]);
            for(int i = 0; i < up; ++i)
            {
                ll tem = v;
                for(int j = 0; j < k; ++j)
                {
                    if(i & (1 << j))
                        tem += a[j];
                    else
                        tem -= a[j];
                }
                MW[i] = max(MW[i], tem);
            }
        }

        /*for(int o = 0; o < up; ++o)
            cout << MW[o] << " ";
        cout << '\n';*/

        for(int o = 0; o < m; ++o)
        {
            scanf("%lld", &v);
            for(int i = 0; i < k; ++i)
                scanf("%lld", &a[i]);
            for(int i = 0; i < up; ++i)
            {
                ll tem = v;
                for(int j = 0; j < k; ++j)
                {
                    if(i & (1 << j))
                        tem += a[j];
                    else
                        tem -= a[j];
                }
                SW[i] = max(SW[i], tem);
            }
        }

        /*for(int o = 0; o < up; ++o)
            cout << SW[o] << " ";
        cout << '\n';*/

        ll res = -INF;
        for(int o = 0; o < up; ++o)
            res = max(res, MW[o] + SW[up - o - 1]);

        printf("%lld\n", res);
    }
    return 0;
}
Donate comment here
0%