洛咕 P4131 [WC2005]友好的生物

---

首先可以发现\(C\)是没有用的，可以乘进所有的权值里面做

考虑没有最后一维的限制，那么两个生物的友好值就是

\(\sum_{i=1}^k|a_i-b_i|\)

这个绝对值就很麻烦了。

但是可以换个思路想，既然是绝对值那么一定\(\geq 0\)，所以两个生物的友好值是

\(\max\left(\sum_{i=1}^k(a_i-b_i)(-1)^{c_i}\right)\)

其中\(c\)取遍所有的01数组。正确性是显然的，因为其他的都没有答案大。

那么这道题\(k\leq 5\)，不考虑最后一维就是\(k=4\)。

上面的式子分开来考虑：

\(\max\left(\sum_{i=1}^ka_i(-1)^{c_i}+\sum_{i=1}^kb_i(-1)^{c_i+1}\right)\)

那么思路就很清晰了，对每个\(c\)记\(\max\left(\sum_{i=1}^kw_i(-1)^{c_i}\right)\)（记为\(Max_c\)）以及取这个最大值的生物，

答案就是\(\max_{c_i+d_i=1}(Max_c+Max_d)\)

但是还有最后一维的限制，所以把生物按照最后一维排序，依次先和Max更新答案，再更新Max。在更新\(Max\)的时候减去最后一维更新，更新答案的时候加上最后一维

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

    int x=0,f=1;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

struct yyb{int a[4],b,i;}s[100010];

int S[100010][1<<4];

il bool operator<(const yyb&a,const yyb&b){return a.b<b.b;}

int Mx[1<<4],f[1<<4],C[6];

int main(){

    int n=gi(),k=gi(),U=(1<<4)-1;

    for(int i=0;i<k;++i)C[i]=gi();

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

        for(int j=0;j<k-1;++j)s[i].a[j]=gi()*C[j];

        for(int j=k-1;j<4;++j)s[i].a[j]=0;

        s[i].b=gi()*C[k-1];

        s[i].i=i;

    }

    k=4;

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

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

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

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

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

                else S[i][j]-=s[i].a[l];

    for(int i=0;i<1<<k;++i)Mx[i]=S[1][i]+s[1].b,f[i]=s[1].i;

    int ans=-1e9,a=0,b=0;

#define chkans(t,_a,_b) {if((t)>ans)ans=(t),a=(_a),b=(_b);}

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

        for(int j=0;j<1<<k;++j)chkans(Mx[U^j]+S[i][j]-s[i].b,s[i].i,f[U^j]);

        for(int j=0;j<1<<k;++j)if(Mx[j]<S[i][j]+s[i].b)Mx[j]=S[i][j]+s[i].b,f[j]=s[i].i;

    }

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

    return 0;

}