[WC2005]友好的生物 题解

· · 题解

洛谷地址
更好体验
和shortcut挺类似的，正解大概能想到一半，先不考虑第 k 位的问题，看一看前 k-1 位
对于那个奇怪的 C ，先把他乘到 d 里面，就可以不考虑了
然后是绝对值
联想一下shortcut那题，一个绝对值有两种拆法 |d_i-d_j|=d_i-d_j 或 |d_i-d_j|=d_j-d_i
那么有没有可能一个错误的拆法出现在了最优解中呢，这是不可能的
若两者都为正数这两种拆法互为相反数，除非都是零，否则会有一个负数，那么最优解肯定不会选择负数那个，也就不会选择不合法的那个
扩展到整数也是一样，最优解一定是合法的
所以我们只要简单地用状压枚举每个绝对值的拆法，打擂台出 j 就好
然后考虑一下第 k 位，看了一下其他人的解法，挺神奇的
但是第 k 位并不能直接加入爆枚中去（反正我没想到方法，取负是错误的，因为爆枚中可能会把它重新取负回来）
所以考虑单调性，如果按照第 k 位升序排序，那么 d_{i,k}-d_{j,k} 就一定是正得了，这样就好贪心很多
具体可以参考代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll n,m,k,a[100001],d[7],sum[100001],ans2,ans1,ans,t1,t2,minn;

struct place {
    ll a[101],id;
    bool operator <(const place&tmp )const {
        return a[m]<tmp.a[m];
    }
}A[1097890];

int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        scanf("%lld",&a[i]);
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            scanf("%lld",&A[i].a[j]);
            A[i].id=i;
            A[i].a[j]*=a[j];
        }
    }
    sort(1+A,1+A+n);
    for(ll s=0;s<=(1<<(m-1));s++){
        ans1=1e10;
        for(ll j=0;j<m-1;j++){
            if(s&(1<<j))d[j+1]=1;
            else d[j+1]=-1;
        }
        for(ll i=1;i<=n;i++){
            ll tmp=0;
            for(ll j=1;j<m;j++){
                tmp+=d[j]*A[i].a[j];
            }
            tmp-=A[i].a[m];
            ans=max(ans,tmp-ans1);
            if(ans==tmp-ans1)t1=A[i].id,t2=minn;
            ans1=min(tmp,ans1);
            if(ans1==tmp)minn=A[i].id;
        }
    }
    cout<<t1<<' '<<t2<<endl<<ans;
}