题目链接

状态压缩

|x-y| 等价于 max(x-y, y-x)

对于k_i的符号是取正还是取负，可以用二进制的0和1来表示，那么每一个主武器和副武器的属性都有 \(2^8\) 种状态，如果主武器的 k_i 取负，那么副武器的k_i一定得取正才行（对应上面的公式），只要我们能分别预先求出主武器和副武器那 \(2^8\) 种状态中，每一种状态的最大取值，那么通过比较主武器的某个k状态x的取值加上副武器中x的取反值的和，取最大值就是答案

i取反 = 与i互补，即 i取反 = \(2^8\) -1-i

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int Maxn = 1e5+10;
const long long INF = 1e18;

int nk[Maxn][10], mk[Maxn][10], ns[Maxn], ms[Maxn];
long long N[40], M[40];

int main(void)
{
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 0; i < n; ++i) {
            scanf("%d", &ns[i]);
            for(int j = 0; j < k; ++j) scanf("%d", &nk[i][j]); 
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d", &ms[i]);
            for(int j = 0; j < k; ++j) scanf("%d", &mk[i][j]);
        }
        for(int i = 0; i < (1<<k); ++i) N[i] = M[i] = -INF;
        
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < (1<<k); ++j) {
                long long tmp = ns[i];
                for(int l = 0; l < k; ++l) {
                    if((j>>l)&1) tmp -= nk[i][l];
                    else tmp += nk[i][l];
                }
                N[j] = max(N[j], tmp);
            }
        }
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < (1<<k); ++j) {
                long long tmp = ms[i];
                for(int l = 0; l < k; ++l) {
                    if((j>>l)&1) tmp -= mk[i][l];
                    else tmp += mk[i][l];
                }
                M[j] = max(M[j], tmp);
            }
        }
        long long ans = -INF;
        for(int i = 0; i < (1<<k); ++i) ans = max(ans, N[i]+M[(1<<k)-1-i]);
        printf("%lld\n", ans);
    }   
    return 0;
 } 

优质内容筛选与推荐>>
1、POJ 2253 Frogger（warshall算法）
2、网络编程三要素之端口号
3、WIN7无法访问共享打印机及文件的解决办法
4、纯资源dll
5、BZOJ 3600 替罪羊树+线段树

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中