自动搬运

查看原文

来自洛谷，原作者为

	蒟蒻丁 大家要好好学习算法竞赛，不然高考寄了就惨了

搬运于2025-08-24 21:56:49，当前版本为作者最后更新于2021-02-21 09:40:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷地址
更好体验
和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;
}