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

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

给定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) 

Read full article from bitmap求哈密顿距离-给定N（1<=N<=100000）个五维的点A(x1,x2,x3,x4,x5)，求两个点X(x1,x2,x3,x4,x5)和Y( - 代码物语-Let code talk - ITeye技术网站