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

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

日目使った布団の集合 最小の不快度の和としたDPを考える．このDPの遷移は となる．しかし，部分集合の部分集合全てを参照し，minを計算すると となってしまう．

使った布団の集合が の部分集合であるとDPのkeyを置き換える．すると，参照するべき要素を限定することができ，遷移は となる．よって， で答えを求めることができる．

#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;  
}