bzoj5068: 友好的生物

题目链接

bzoj5068: 友好的生物

题解

最大化这个东西\(\sum_{i=1}^{k-1} | a_{x,i}-a_{y,i} | - | a_{x,k}-a_{y,k} |\)

去掉绝对值号，也就是就是求这个式子 \(\sum_{i=1}^{k-1}±(a_{x,i}-a_{y,i}) - | a_{x,k} - a_{y,k} |\) 的最大值

对与前面的 \(i\) 式取 正负号 一定会有一个方案使每个 \(a_{x,i}-a_{y,i}\) 不负

装压枚举每个\(i\)的符号,对于 \(a_{x,k}\) 从小到大排序，维护前缀最小值更新答案

代码

#include<cmath>

#include<cstdio>

#include<algorithm>

inline int read() {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9'){if(c == '-')f = - 1; c = getchar(); }

    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();

    return x * f;

}

#define INF 0x3f3f3f3f

int n,k;

struct A  {

    int d[10],id;

    bool operator < (const A &a)const {

        return d[k] < a.d[k];

    }

} a[100007];

int c[76];

int main() {

    n = read(),k = read() - 1;

    for(int i = 0;i <= k;++ i) c[i] = read();

    for(int i = 1;i <= n;++ i) {

        a[i].id = i;

        for(int j = 0;j <= k;++ j) a[i].d[j] = read(),a[i].d[j] *= c[j];

    }

    std::sort(a + 1,a + n + 1);

    int ans = 0,id1,id2;

    for(int s = 0;s < (1 << k); ++ s) {

        int minn = INF, id;

        for(int i = 1;i <= n;++ i) {

            int ss = 0;

            for(int j = 0;j < k;++ j)

                if(s & (1 << j)) ss += a[i].d[j];

                else ss -= a[i].d[j];

            ss -= a[i].d[k ];

            if(ans  < ss - minn) ans = ss - minn,id1 = a[i].id,id2 = id;

            if(minn > ss) minn = ss,id = a[i].id;

        }

    }

    printf("%d\n",ans);

    return 0;

}