HDU 4666 最远曼哈顿距离

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4666

关于最远曼哈顿距离的介绍：

http://blog.csdn.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 ;

 }

巴特西

HDU 4666 最远曼哈顿距离

最新文章

热门文章