Code Festival 2017 Final D - Zabuton

問題

n人が順番に座布団を積んでいく
i人目は自分の番が回ってきた時に既に積まれた座布団がa[i]枚以下である場合はちょうどb[i]枚の座布団を積む
n人の並び順を工夫することによって最大で何人が座布団を積むことができるか

1 <= n <= 5000
0 <= a[i] <= 10^9
1 <= b[i] <= 10^9

解法

「うまく並べればn人全員が座布団を積める」場合はa[i]+b[i]の昇順に並べるのが最善であることが証明できる(解説pdfより)
ソートしてから
dp[i][j]: i人目まででj人が座布団を置く場合に積み重なる座布団の枚数の最小値
とすれば解ける

ソートしてからdpするシリーズ
この問題はサンプル2のおかげで(式変形をしなくても)予想しやすい方？
変数が2つある問題はとりあえず±a±bの値は疑うべきらしい

#define int long long

int n, a[5050], b[5050], dp[5050][5050], res;
pair<int,int> p[5050];

signed main() {
	cin >> n;
	rep(i,n) {
		cin >> a[i] >> b[i];
		p[i] = {a[i]+b[i], i};
	}
	sort(p, p+n);
	rep(i,5050) rep(j,5050) dp[i][j] = 1ll<<60;
	dp[0][0] = 0;
	rep(i,n) rep(j,n) if (dp[i][j]!=1ll<<60) {
		int id = p[i].second;
		chmin(dp[i+1][j], dp[i][j]);
		if (dp[i][j]<=a[id]) chmin(dp[i+1][j+1], dp[i][j] + b[id]);
	}
	rep(i,n+1) if (dp[n][i]!=1ll<<60) res = i;
	cout << res << endl;
}