SRM 261 DIV1 Hard StackingBoxes

問題 Editorial

問題

重さweightと許容重量capacityが設定された箱がNつある。
箱は他の箱の上にいくつでも積み上げられるが、どの箱も上に乗っている箱の重量の総和が許容重量以下でなければいけない。
積み上げられる最大個数を求めよ

• 1 <= N <= 1250くらい
• 1 <= weight[i] <= 10^5
• 1 <= capacity[i] <= 10^9

解答

Editorialを参考にした。あまりよくわかっていない。
まず、最大なら(weights[i] + capacity[i] > weights[i+1] + capacity[i+1])が成立する(なぜかはあまりよくわかっていない)
あとは((i番目からで * m個積むときの)最小重み)というDPでできる

コメント

なんかうまいやり方。今のところこういうのを出来る気がしない。どうやって考えればいいんだろうか？
少なくともこの類問はできるように、この解答は覚えておこう。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#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 each(it,o) for(__typeof((o).begin()) 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 0x3f3f3f3f
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef vector<string> vs;
int dp[1255][1255];
struct StackingBoxes {
	vi parse(vs v) {
		vi r;
		each(i, v) {
			stringstream ss(*i); int x;
			while(ss >> x) r.pb(x);
		}
		return r;
	}
	static bool cmp(pii x, pii y) {
		return x.first + x.second > y.first + y.second;
	}
	int n;
	vpii wc;
	int rec(int i, int m) {
		if(dp[i][m] != -1) return dp[i][m];
		int r = INF;
		if(i == n) r = m == 0 ? 0 : INF;
		else {
			r = min(r, rec(i+1, m));
			if(m && wc[i].second >= rec(i+1, m-1))
				r = min(r, wc[i].first + rec(i+1, m-1));
		}
		return dp[i][m] = r;
	}
	int highestStack(vector <string> weight, vector <string> canCarry) {
		vi ws = parse(weight), cs = parse(canCarry);
		n = ws.size();
		wc.clear(); rep(i, n) wc.pb(mp(ws[i], cs[i]));
		sort(all(wc), cmp);
		int r = 0;
		mset(dp, -1);
		rer(i, 0, n) if(rec(0, i) != INF) r = max(r, i);
		return r;
	}
};