https://lydsy.com/JudgeOnline/problem.php?id=5068
分析：
考虑如何去掉绝对值符号。
因为k很小，所以可以直接枚举k个数的正负性，这样一定会取到一个全是正的情况。
$\sum\limits_{i=1}^{k-1} | a_{x,i}-a_{y,i} | - | a_{x,k}-a_{y,k} |$
对于后面那一部分，直接按$a_{x,k}$排序即可，从小到的到大的枚举，前面的一定比后面的小。
前面那一部分，枚举k-1个的正负性：
$\sum\limits_{i=1}^{k-1} \pm a_{x,i} - \sum\limits_{i=1}^{k-1} \pm a_{y,i}$
然后扫一遍，对前面取最小的即可。
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<iostream> 5 #include<cmath> 6 #include<cctype> 7 #include<set> 8 #include<queue> 9 #include<vector> 10 #include<map> 11 using namespace std; 12 typedef long long LL; 13 14 inline int read() { 15 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; 16 for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; 17 } 18 19 const int N = 100005; 20 21 int c[10], n, k; 22 struct Node{ 23 int x, d[6]; 24 bool operator < (const Node &A) const { 25 return d[k] < A.d[k]; 26 } 27 }A[N]; 28 29 int main() { 30 n = read(), k = read() - 1; 31 for (int i = 0; i <= k; ++i) c[i] = read(); 32 for (int i = 1; i <= n; ++i) 33 for (int j = 0; j <= k; ++j) A[i].d[j] = read() * c[j]; 34 sort(A + 1, A + n + 1); 35 int ans = 0, S = (1 << k) - 1; 36 for (int s = 0; s <= S; ++s) { 37 int Mn = 1e9, now; 38 for (int i = 1; i <= n; ++i) { 39 now = 0; 40 for (int j = 0; j < k; ++j) { 41 if ((s >> j) &1) now += A[i].d[j]; 42 else now -= A[i].d[j]; 43 } 44 now -= A[i].d[k]; 45 ans = max(ans, now - Mn); 46 Mn = min(Mn, now); 47 } 48 } 49 cout << ans; 50 return 0; 51 }
原文：https://www.cnblogs.com/mjtcn/p/10046836.html