SRM415: CollectingPostmarks

(問題概要)
n (<=32) 個のポストカードがあり、価格(<= 30000000)と価値(<= 30000000)が与えられる。
幾つかのポストカードをすでに持っている。
持っているポストカードは同じ価格で売ることができる。
価値Kを得るにはいくら追加でお金がいるか。

(解法)
とりあえず持ってるのは全部売って、一から考えると楽。
問題形式的には典型的ナップザック問題に見えるが、価格と価値が高すぎてDPができない。
半分に分けてそれぞれ全列挙してやることでn * 2 ^ (n / 2)くらいの計算量になり解ける。
前回との難易度のギャップがやばい。
コーディングミスでめっちゃ時間かかった。

#include <algorithm>
#include <cstdio>
#include <cassert>
#include <map>
#include <climits>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <numeric>
typedef long long ll;

#include <queue>
#include <set>
#include <iostream>
#include <sstream>

using namespace std;

class CollectingPostmarks {
public:
  int amountOfMoney(vector <int> prices, vector <int> have, vector <int> values, int K);
};

int CollectingPostmarks::amountOfMoney(vector <int> prices, vector <int> have, vector <int> values, int K){
  const ll sum = accumulate(values.begin(), values.end(), 0ll);
  if(sum < K) return -1;

  const int n = prices.size();
  int pp = 0;
  REP(i,have.size()) pp += prices[have[i]];

  const int nn = (n + 1) / 2;
  const int mm = n - nn;

  map<int, int> memo1;
  REP(i, 1<<nn){
    int p = 0;
    int v = 0;
    REP(j,nn) if(i & (1 << j)){
      p += prices[j];
      v += values[j];
    }
    if(memo1.count(v)){
      memo1[v] = min(memo1[v], p);
    }else{
      memo1[v] = p;
    }
  }

  map<int, int> memo2;
  REP(i, 1<<mm){
    int p = 0;
    int v = 0;
    REP(j,mm) if(i & (1 << j)){
      p += prices[nn + j];
      v += values[nn + j];
    }
    if(memo2.count(v)){
      memo2[v] = min(memo2[v], p);
    }else{
      memo2[v] = p;
    }
  }

  vector<pair<int, int> > m1(memo1.begin(), memo1.end());
  vector<pair<int, int> > m2(memo2.begin(), memo2.end());

  sort(m1.begin(), m1.end()); sort(m2.begin(), m2.end());

  for(int i = m1.size() - 1; i > 0; i--)
    m1[i - 1].second = min(m1[i - 1].second, m1[i].second);
  for(int i = m2.size() - 1; i > 0; i--)
    m2[i - 1].second = min(m2[i - 1].second, m2[i].second);

  int ans = INT_MAX;
  REP(i,m1.size()){
    const int p = m1[i].second;
    const int v = m1[i].first;

    if(v >= K){
      ans = min(ans, p);
    }else{
      const int idx = lower_bound(m2.begin(), m2.end(), make_pair(K - v, 0)) - m2.begin();
      if(idx != (int)m2.size()){
	ans = min(ans, p + m2[idx].second);
      }
    }
  }

  return max(0, ans - pp);
}