hdu4666 Hyperspace ——曼哈顿距离

link:http://acm.hdu.edu.cn/showproblem.php?pid=4666 这题学会了怎么处理曼哈顿距离。 比如维数是k，那么每个点有2^k个状态，求出在每个状态下，所有点的最大值，最小值，求他们的差，从中找到最大值就行。 开始觉得不好处理的是，删除的时候怎么办。比如要删除一个点，我可以在2^k个中的每个状态里面先找到这个点在这个状态下的值，删除这个值就行了。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
multiset<int> a[44];
int sad[66666][10],will[66666][44];
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif // ONLINE_JUDGE
    int q,k;
    while (~scanf("%d%d",&q,&k))
    {
        int apple=1<<k;
        for(int i=0;i<44;++i) a[i].clear();
        for(int i=0;i<q;++i)
        {
            int op; scanf("%d",&op);
            if(op==0)
            {
                for(int j=0;j<k;++j)
                {
                    scanf("%d",&sad[i][j]);
                }
                for(int j=0;j<apple;++j)
                {
                    int s=0;
                    for(int pear=0;pear<k;++pear)
                    {
                        if(j&(1<<pear)) s+=sad[i][pear];
                        else s-=sad[i][pear];
                    }
                    will[i][j]=s;
                    a[j].insert(s);
                }
            }
            else
            {
                int nu; scanf("%d",&nu);
                for(int j=0;j<apple;++j)
                {
                    multiset<int>::iterator it;
                    it=a[j].find(will[nu-1][j]);
                    if(it!=a[j].end())
                        a[j].erase(it);
                }
            }
            int ans=0;
            for(int j=0;j<apple;++j)
            {
                if(a[j].size()>1)
                {
                    int big=*(--a[j].end()),
                    small=*(a[j].begin());
//                    printf("big=%d small=%d\n",big,small);
                    if(big-small>ans) ans=big-small;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

o(╯□╰)o