SRM 415 DIV1 Medium CollectingPostmarks

http://community.topcoder.com/stat?c=problem_statement&pm=9958&rd=13506

回答

他の人の回答を見た。
まず、持ってるものは売ってから買っても同じなので、まず全部売ってから考える。
ナップザック問題にできて、値の範囲的にDPはできないので指数時間がかかる。
半分を全列挙してから、ソートして、
もう半分を全列挙し、それと最初の半分との和で二分探索をし、その価値である最小のpriceを求める。これは最初にソートした後に次のようにすればいいらしい。

sort(q, q+qn);
//valueに基づき、最初の半分の全(value, price)をソートする
for(int i = qn-1; i > 0; i --) q[i-1].second = min(q[i-1].second, q[i].second);
//q' i = min (q i) (q' (i+1))
//valueでソートされていることに注意すると、
//つまりvalueが小さいのにもかかわらずpriceが大きいものは、
//大きい方のvalueのやつでできるよね、っていう感じ

それらの最小値を取る。

コメント

こういう解き方は知らなかった。頻出で、知らなかったらわからないと思うので、しっかり覚えておきたい

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);(i)++)
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);(i)++)
#define aut(r,v) typeof(v) r = (v)
#define each(it,o) for(aut(it,o.begin()); it != (o).end(); it ++)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x7f1f1f1f
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii;

pii q[1<<16];
struct CollectingPostmarks {
	int amountOfMoney(vector <int> prices, vector <int> have, vector <int> values, int K) {
		int n = prices.size();
		int hav = 0; each(i, have) hav += prices[*i];
		int m = n/2;
		int qn = 0;
		rep(i, 1<<m) {
			int w = 0, p = 0;
			rep(j, m) if(i & (1<<j)) p += prices[j], w += values[j];
			q[qn++] = mp(w, p);
		}
		sort(q, q+qn);
		for(int i = qn-1; i > 0; i --) q[i-1].second = min(q[i-1].second, q[i].second);
		int r = INF;
		rep(i, 1<<(n-m)) {
			int w = 0, p = 0;
			rep(j, (n-m)) if(i & (1<<j)) p += prices[m+j], w += values[m+j];
			if(q[qn-1].first+w < K) continue;
			//二分探索
			int l = -1, u = qn;
			while(u - l > 1) {
				int m = (l + u) / 2;
				if(q[m].first + w >= K) u = m;
				else l = m;
			}
			r = min(r, p + q[u].second);
		}
		return r == INF ? -1 : max(0, r - hav);
		//見た
	}
};