AOJ 1295 Cubist Artwork
問題
Cubist Artwork | Aizu Online Judge
箱を並べる。これを前から見ると D 列のキューブが X1, X2, ..., XD 個並んでいるように見え, 横から見ると W 列のキューブが Y1, Y2, ..., YW 個並んでいるように見える。
これを満たすようなキューブの並べ方のうち, 必要なキューブの数が最小のものは, いくつのキューブを必要とするか(条件を満たす並べ方が存在することは保証されている)。
解法
サンプルにいろいろな例が書いてあるので, 自分で書いて実験してみましょう。すると, 以下のような解法でいけることがわかります。
- Xi と Yj が一致していたら, (i, j) 座標に Xi を置けば OK
- そうでない場合は, いい感じのところ(Xi の値が一番大きいところにカモフラージュするようにする)に置けば, 少なくとも Xi (1 <= i <= D) の部分は合う
- 後は Yi を埋める
bool done[22]; int main() { cin.tie(0); ios::sync_with_stdio(false); int W, D; while (cin >> W >> D) { if (W==0 && D==0) break; vi X(W), Y(D); for (int i = 0; i < W; i++) cin >> X[i]; for (int i = 0; i < D; i++) cin >> Y[i]; memset(done, false, sizeof(done)); int ans = 0; for (int i = 0; i < W; i++) { ans += X[i]; for (int j = 0; j < D; j++) { if (!done[j] && X[i] == Y[j]) { done[j] = true; break; } } } for (int i = 0; i < D; i++) { if (!done[i]) ans += Y[i]; } cout << ans << endl; } return 0; }