點(diǎn)擊打開hdu 4666

思路:n維空間計(jì)算最遠(yuǎn)的曼哈頓距離
分析:
1 這一題和poj2926很像，但是poj那題是靜態(tài)的而這邊則是動(dòng)態(tài)的，對(duì)于靜態(tài)的話我們知道只要去求出2^n狀態(tài)下的最大值和最小值，然后求最大的差值即為ans
2 但是對(duì)于動(dòng)態(tài)的來說我們需要去維護(hù)每一個(gè)狀態(tài)的最大值和最小值，因此我們利用multiset來保存每一個(gè)狀態(tài)下的所有的值，因?yàn)閙ultiset是自動(dòng)排序那么我們就可以很好的求出最大值和最小值
3 注意這邊保存點(diǎn)不能夠用struct要用數(shù)組，因?yàn)槊看伪４嬖诮Y(jié)構(gòu)體里面的話回去調(diào)用構(gòu)造函數(shù)時(shí)間開銷很大

代碼:

?

#include<set> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std;const int N = 5; const int MAXN = 60010;int n , k , pos; int numId[MAXN]; int mat[MAXN][N]; multiset<int> mst[1<<N];void init(){pos = 0;for(int i = 0 ; i < (1<<k) ; i++)mst[i].clear(); }int getSum(int id , int s){int sum = 0;for(int i = 0 ; i < k ; i++){if(s&(1<<i)) sum += mat[id][i];elsesum -= mat[id][i];}return sum; }void add(){for(int i = 0 ; i < (1<<k) ; i++){int sum = getSum(pos , i);mst[i].insert(sum);} }void remove(int id){for(int i = 0 ; i < (1<<k) ; i++){int sum = getSum(id , i);multiset<int>::iterator it;it = mst[i].find(sum);mst[i].erase(it);} }int getAns(){multiset<int>::iterator it;int tmp;int ans = 0;for(int i = 0 ; i < (1<<k) ; i++){it = mst[i].end(); it--;tmp = *it;it = mst[i].begin(); tmp -= *it;ans = max(ans , tmp);}return ans; }int main(){int mark , x , y;while(scanf("%d%d" , &n , &k) != EOF){init();for(int i = 0 ; i < n ; i++){scanf("%d" , &mark);if(mark == 0){numId[i+1] = pos;for(int j = 0 ; j < k ; j++)scanf("%d" , &mat[pos][j]); add();pos++;}else{scanf("%d" , &x);remove(numId[x]); } printf("%d\n" , getAns());}}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/bbsno1/p/3257826.html

總結(jié)

以上是生活随笔為你收集整理的hdu 4666 Hyperspace的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。