ICPC2016 模擬国内予選B E ぼくのかんがえたさいきょうのおふとん

問題

2016/Practice/模擬国内予選B/問題文とデータセット - ACM-ICPC Japanese Alumni Group

解法

使われているお布団の組み合わせが bitmask とする。この組み合わせでできる最小のコストを dp[bitmask] とする。ここに新しくお布団 i を下に差し込んでコストを下げられるかどうかを調べ、dp[bitmask & (1<

#include <bits/stdc++.h>
using namespace std;

int N, M;

int64_t solve(const vector<int> &s, const vector<int> &d) {
  // dp[bitmask] := bitmask の組み合わせで出来る最小のコスト
  vector<int64_t> dp((1 << N), 1e9);
  queue<int> que;
  que.push(0);
  dp[0] = accumulate(d.begin(), d.end(), 0);
  while (!que.empty()) {
    int bitmask = que.front();// 使われているお布団の組み合わせ
    que.pop();
    int64_t sum = 0;
    for (int i = 0; i < N; ++i)
      if (bitmask & (1 << i)) sum += s[i];

    for (int i = 0; i < N; ++i) {
      if (bitmask & (1 << i)) continue;//既にお布団iが含まれているならスルー

      // お布団iを新たに追加する場合を考える
      int64_t cost = dp[bitmask];
      for (int m = 0; m < M; ++m) {
        if (d[m] <= sum) continue;//お布団iを使わないほうが良い場合はスルー
        if (d[m] - sum > abs(d[m] - (sum + s[i]))) {
          cost -= (d[m] - sum);
          cost += abs(d[m] - (sum + s[i]));
        }
      }

      // 最小コストを更新する
      if (dp[bitmask | (1 << i)] <= cost) continue;
      dp[bitmask | (1 << i)] = cost;
      que.push(bitmask | (1 << i));
    }
  }

  return *min_element(dp.begin(), dp.end());
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  while (true) {
    cin >> N >> M;
    if (N == 0) break;
    vector<int> s(N);
    vector<int> d(M);
    for (int i = 0; i < N; ++i) cin >> s[i];
    for (int i = 0; i < M; ++i) cin >> d[i];
    cout << solve(s, d) << endl;
  }
}