题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4666
关于最远曼哈顿距离的介绍：
http://blog.****.net/taozifish/article/details/7574294/
别人的解题报告链接：
http://www.cnblogs.com/kuangbin/archive/2013/08/13/3255752.html
我的解释：
先看一对点，两个点的坐标分别为x(x1,x2,x3,….,xk),y(y1,y2,y3,……,yk).
其曼哈顿距离为d = |x1-y1| + |x2-y2| +…..+|xk-yk|.
在去绝对值后，对于点x,一共有2^k种可能的组合。
所以，在求n个点时，用1表示正号，0表示负号，像状态压缩一样，把所有点的可能都存起来 ，求出每个点在每种状态下的值。如下面三个点的坐标为（2,3），(3,4),(4,5)。它有四种状态，四种状态下对应的值为：
（+，+）5, 7,9
（+，-）-1，-1，-1
（-，+）1，1 ，1
（-，-）-5，-7，-9
最大值为在某种状态下的最大值减去最小值。为什么会是同种状态下呢，看上面曼哈顿距离的计算公式能发现，如果|xi-yi|为正，那么化为xi – yi，x和y对应的分量同号，如果为负，那么化为-xi – (-yi),同样是同号的。式子最终将会化成k1*x1+k2*x2 + ``` + kn*xn – (k1*x1+k2*x2+````+kn*xn)。ki为符号，可正可负。
要想使这个式子最大，自然是某种状态下的最大值减最小值。因为|a-b|>=a-b, |a-b|>=b-a.所以虽然有些符号其实是弄错了的，但是不会影响最大值的得出。
注意：这是我第一次使用multiset，关于删除,multiset有至少两种方法，一种是以键值删除，一种是根据迭代器位置删除···
我一激动。用了第一种，结果一直WA···
还有就是关于全局变量和局部变量，如果既定义了k为全局变量，又在main函数中定义了k为局部变量，那么k就是一个局部变量了，编译器对于这种错误是不会报错的····
其实，我不是很理解这个算法，我是抄的····
还有set<int>se.插入后是已经排好序了的，如果想调用其中的最大值，那么应该写
multiset<int>::iterator it;
it = se.end();
--it;
int t2 = (*it);
最小值应该为int t1 = *se.begin();
贴代码：
#include <cstdio>
#include <set>
#define N 60010
using namespace std;
int x[N][];
int d,k;
multiset<int> ms[];
void solve(int a[],int flag)
{
for(int i=; i<d ; ++i)
{
int s=;
for(int j=; j<k; ++j)
{
if(i&(<<j)) s += a[j];
else s -= a[j];
}
if(flag) ms[i].insert(s);
else
{
multiset<int>::iterator it = ms[i].find(s);
ms[i].erase(it);
}
}
}
int main()
{
// freopen("in.c","r",stdin);
int q;
while(~scanf("%d%d",&q,&k))
{
d = <<k;
for(int i=; i<d; ++i) ms[i].clear();
for(int i=; i<=q; ++i)
{
int od;
scanf("%d",&od);
if(od == )
{
for(int j=; j<k; ++j)
scanf("%d",&x[i][j]);
solve(x[i],true);
}
else
{
int p;
scanf("%d",&p);
solve(x[p],false);
}
int ans =;
for(int j=; j<d; ++j)
{
int t1 = *(ms[j].begin());
multiset<int>::iterator it;
it = ms[j].end();
--it;
int t2 = (*it);
if(t2-t1 > ans) ans= t2-t1;
}
printf("%d\n",ans);
}
}
return ;
}