ferinの競プロ帳

競プロについてのメモ

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

問題ページ
ぬくもり需要 d をソートしておくと,おふとんを増やす操作のみに置き換えられる.したがっておふとんを積む順番は記録せずに,使ったおふとんの集合だけ記録すればよくなる.

\text{dp} \lbrack i日目 \rbrack  \lbrack 使った布団の集合j \rbrack  = 最小の不快度の和としたDPを考える.このDPの遷移は \text{dp} \lbrack i \rbrack  \lbrack j \rbrack  = \min_{k \subseteq j} (dp \lbrack i-1 \rbrack  \lbrack k \rbrack ) + |\sum_{x\in j} s \lbrack x \rbrack  - d \lbrack i \rbrack | となる.しかし,部分集合の部分集合全てを参照し,minを計算すると O(3^N) となってしまう.

使った布団の集合が j の部分集合であるとDPのkeyを置き換える.すると,参照するべき要素を限定することができ,遷移は \text{dp} \lbrack i \rbrack  \lbrack j \rbrack  = \min(\text{dp} \lbrack i-1 \rbrack  \lbrack j \rbrack +|\sum_{x\in j} s \lbrack x \rbrack  - d \lbrack i \rbrack |, \text{dp} \lbrack i \rbrack  \lbrack j\setminus\{k\} \rbrack  (k\in j)) となる.よって,O(NM2^N) で答えを求めることができる.

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
ll dp[105][1LL<<15];  
void solve() {  
    ll n, m;  
    cin >> n >> m;  
    if(n == 0) exit(0);  
    vector<ll> s(n), d(m);  
    REP(i, n) cin >> s[i];  
    REP(i, m) cin >> d[i];  
    sort(ALL(d));  
  
    FOR(i, 1, m+1) REP(j, 1LL<<n) dp[i][j] = INF;  
    REP(j, 1LL<<n) dp[0][j] = 0;  
    REP(i, m) REP(j, 1LL<<n) {  
        ll sum = 0;  
        REP(k, n) if(j&1LL<<k) sum += s[k];  
        chmin(dp[i+1][j], dp[i][j] + abs(sum-d[i]));  
        REP(k, n) if(j&1LL<<k) {  
            ll x = j ^ (1LL<<k);  
            chmin(dp[i+1][j], dp[i+1][x]);  
        }  
    }  
  
    ll ret = INF;  
    REP(i, 1LL<<n) chmin(ret, dp[m][i]);  
    cout << ret << endl;  
}  
  
int main(void) {  
    while(1) solve();  
  
    return 0;  
}