もふふろぐ

AOJ 2749 ぼくのかんがえたさいきょうのおふとん

aojcompetitivecppprogram

ICPCの模擬国内予選2016から「ぼくのかんがえたさいきょうのおふとん」です。おふとんいっぱいの問題だったので解法をまとめました。

方針

押入れとベッドはいずれもスタックですが出し入れの枚数に制限ありません。このことから、ベッドにおふとんを出す行為は、押入れに重ねたおふとんの上からX枚（0 ≤ X ≤ N）を選ぶ行為であると読みかえることができます。さらに、M日間のぬくもり需要の順序を無視できることもわかります。

M日間のぬくもり需要を昇順に並べ替えると、最適なおふとんの枚数Xも昇順になります。つまりi日目（0 < i ≤ M）に行われる操作は、i - 1日目に選んでいたおふとんに、まだ選ばれていないおふとん0枚以上を追加することであると言えます。そしてi - 1日目までに選んだおふとんの順序を無視できることもわかりました。

1 ≤ N ≤ 15であることから、おふとんの選び方をビットで表すことができます（0 ≤ j < 2^N）。これによってdp[i日目][おふとん集合j] = i日目にjを選ぶときの不快度の総和の最小としたbit DPによってO(MN 2^N)で解くことができました。

解答

おふとん集合とそのぬくもりの和の対応（sum[1 << 15]）をあらかじめ計算しています。

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  for (int n, m; cin >> n >> m, n;) {
    vector<int> s(n), d(m);
    for (auto &e : s) cin >> e;
    for (auto &e : d) cin >> e;
    sort(d.begin(), d.end());

    vector<int> sum(1 << n);
    for (int j = 0; j < 1 << n; j++) {
      for (int k = 0; k < n; k++) {
        if (j & 1 << k) sum[j] += s[k];
      }
    }

    vector<int> dp(1 << n);
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 1 << n; j++) {
        dp[j] += abs(sum[j] - d[i]);
      }
      for (int j = 0; j < 1 << n; j++) {
        for (int k = 0; k < n; k++) {
          dp[j] = min(dp[j], dp[j & ~(1 << k)]);
        }
      }
    }
    cout << dp[(1 << n) - 1] << endl;
  }
}

良いおふとんでした。