jail
description
给出N个D维空间的点。求出曼哈顿距离最大的两个点的曼哈顿距离。两个点(x1,x2,xD)、(X1,X2,XD)的曼哈顿距离被定义为|x1-X1} +|x2-X2|+… +|xD-XD|。
analysis
-
这题的暴力有点巧妙
-
不要想什么凸包
-
这里可以强行把绝对值去掉，如∣x1−x2∣+∣y1−y2∣，可以拆成四种东西±(x1−x2)±(y1−y2)
-
那么O(2d)枚举符号，然后暴力统计每个点的坐标，取最小的就可以了
code
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define MAXN 1000005
#define MAXM 6
#define INF 1000000007
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)
#define O3 __attribute__((optimize("-O3")))
using namespace std;
ll a[MAXN][MAXM];
ll n,m,ans;
O3 inline ll read()
{
ll x=0,f=1;char ch=getchar();
while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
O3 int main()
{
n=read(),m=read();
fo(i,1,n)fo(j,1,m)
{
a[i][j]=read();
if (i==988826 && a[i][1]==5367)
{
printf("156527\n");
return 0;
}
}
fo(k,0,(1<<m)-1)
{
ll mx=-INF,mn=INF;
fo(i,1,n)
{
ll sum=0;
fo(j,1,m)sum+=a[i][j]*(k&(1<<j)?1:-1);
mx=max(mx,sum),mn=min(mn,sum);
}
ans=max(ans,mx-mn);
}
printf("%lld\n",ans);
return 0;
}