AOJ-1295 : Cubist Artwork
ブロックを使って、示された形のオブジェクトを作る。
作るオブジェクトの形の正面から見た図と側面から見た図が与えられる。
上記の形を満たすオブジェクトを作る上で最小のブロック数を求めよ。
入力はそれぞれの向きから見たときのN番目の位置の高さである。
解法としては、正面から見たときの高さと側面から見たときの高さで同じものがあればその位置のブロックは1本で両方実現できるため省く。その後、それぞれの配列でペアが見つからなかった高さの位置はそのままブロックを立てれば良いため、残りを全て足し込む。上記でブロックの最少数が求まる。
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1295 #include<iostream> #include<map> #include<vector> #include<algorithm> #include<cmath> #include<climits> #include<ctime> #include<cstring> #include<numeric> #define ALL(v) (v).begin(),(v).end() #define REP(i,p,n) for(int i=p;i<(int)(n);++i) #define rep(i,n) REP(i,0,n) #define dump(a) (cerr << #a << "=" << (a) << endl) #define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl; using namespace std; int W,D; int main() { while(cin >> W >> D && W) { vector<int> width(W,0); vector<int> height(D,0); rep(i,W){ cin >> width[i]; } rep(i,D){ cin >> height[i]; } int ans=0; rep(w,W) { rep(h,D) { if(width[w] == height[h]) { ans += width[w]; width[w] = 0; height[h] = 0; break; } } } ans += accumulate(ALL(width),0); ans += accumulate(ALL(height),0); cout << ans << endl; } return 0; }