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