戳还有集训队写的的题解~
大概思路：
1.把c[j]乘入属性中。乘完后求的即是：
2.对于前k-1个属性和第k个属性分别讨论，即
3.枚举符号序列，最优的情况一定包含在之内 。
4.把生物按照第k个属性的大小排序，保证了后面的数第k种属性大于前面的，这样减出来第k个属性的差值一定是负值，满足条件。
#include<bits/stdc++.h> #define mod 1000000007 #define LL long long #define N 100003 #define INF 2100000000 using namespace std; int read() { int f=1,x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x*f; } int c[10],k; struct animal{ int a[10],ord; }p[N]; bool cmp(const animal &x,const animal &y) { return x.a[k]<y.a[k]; } int main() { int n=read();k=read(); for(int i=1;i<=k;++i)c[i]=read(); for(int i=1;i<=n;++i) for(int j=1;j<=k;++j) { p[i].a[j]=read();p[i].a[j]*=c[j];p[i].ord=i;//直接将c[j]乘入 } sort(p+1,p+1+n,cmp); int ans=0,t1,t2,minid; for(int i=(1<<(k-1))-1;i>=0;--i)//枚举符号序列，最优的情况一定包含在之内 { int minn=INF; for(int j=1;j<=n;++j) { int num=0; for(int l=k-1;l>=1;--l)num=num+((i&(1<<(l-1)))?p[j].a[l]:(-p[j].a[l]));//前k-1个 num-=p[j].a[k];//减一个更大的就满足了负号要求了 if(num-minn>ans){ans=num-minn;t2=minid,t1=p[j].ord;}//更新ans时是用num-minn判，因为求的是两个生物的属性差 if(minn>num){minn=num,minid=p[j].ord;}//minn保存最小的属性和 } } printf("%d",t1,t2,ans); }