Massive Algorithms: bitmap求哈密顿距离-给定N（1<=N<=100000）个五维的点A(x1,x2,x3,x4,x5)，求两个点X(x1,x2,x3,x4,x5)和Y( - 代码物语-Let code talk

给定N（1<=N<=100000）个五维的点A(x1,x2,x3,x4,x5)，求两个点X(x1,x2,x3,x4,x5)和Y(y1,y2,y3,y4,y5)，

* 使得他们的哈密顿距离（d=|x1-y1| + |x2-y2| + |x3-y3| + |x4-y4| + |x5-y5|）最大。|x|=abs(x)。

* 第一种方法当然是暴力遍历一次，求得最大值

* 第二种方法借助bitmap

* 在网上找了两个相关的资料：

* http://www.cppblog.com/sonicmisora/archive/2009/09/14/96143.aspx

* http://wenku.baidu.com/view/1e51750abb68a98271fefaa8.html

* 我觉得这两个资料都不好理解

* 我的理解如下：

* 1.

* 这道题目里面，使用bitmap的关键是这个：

* 先看二维的点，我们约定形如Xij下标的数字(ij)是二进制，0表示正数，1表示负数，令

* X00= x1 + x2

* X01= x1 - x2

* X10= - x1 + x2

* X11= - x1 - x2

* 用一个一维数组a保存这四个值，即a[0]=X00,a[1]=X01,a[2]=X10,a[3]=X11

* 有N个点，那么就有二维数组：A[N][S],(S=00,01,10,11)

Labels