傳送門

以二維的兩個點\((x1,y1),(x2,y2)\)為例，那么他們之間的曼哈頓距離肯定為一下四個之一\((x1-x2)+(y1-y2)\),\((x2-x1)+(y1-y2)\),\((x1-x2)+(y2-y1)\),\((x2-x1)+(y2-y1)\)，而且為這四個里面最大的

然后搞一搞可以變成下面的樣子
\((x1+y1)-(x2+y2)\),\((x1-y1)-(x2-y2)\),\((-x1+y1)-(-x2+y2)\),\((-x1-y1)-(-x2-y2)\)

發現每一個形式里面每一維坐標前的符號都是相等的。那么我們可以枚舉符號的狀態，然后找到在這個狀態下的最大的和最小的數，用兩數相減去更新答案

不難證明高維的情況也可以轉化成這樣，這里就不證了才不是因為懶呢

upd:或者也可以認為兩個點各坐標的符號相反，于是只要對于每一個狀態維護它的最大值，然后用互補狀態的最大值之和更新答案就可以了

//minamoto #include<bits/stdc++.h> #define R register #define inf 0x3f3f3f3f #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;} template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } const int N=1e6+5; const int D[]={2,4,8,16}; int sum[19][N],a[N][5],n,m,ans,lim,mn,mx; int main(){ // freopen("testdata.in","r",stdin);n=read(),m=read(),lim=D[m-1];fp(i,1,n){fp(j,1,m)a[i][j]=read();fp(k,0,lim-1)fp(j,1,m)sum[k][i]+=(k>>(j-1)&1)?a[i][j]:-a[i][j];}fp(k,0,lim-1){mn=inf,mx=-inf;fp(j,1,n)cmax(mx,sum[k][j]),cmin(mn,sum[k][j]);cmax(ans,mx-mn);}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/bztMinamoto/p/10151307.html

總結

以上是生活随笔為你收集整理的P1648 看守的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。