UTPC2011 E: ファーストアクセプタンス

keyword

動的計画法　C++

問題概要

問題がN(<1000)問ある。各問題ごとに解くのに必要な時間A[i]と自分以外がfirst acceptされる時間B[i]が与えられる。最大で難問first acceptを取れるか求める。

解法

解く問題が決まっているならB[i]の小さい順に解くのが最善だと分かる。従ってB[i]をkeyにしてsortしてDPで解ける。dp[i][j] = {index i以下の問題で解いたのがj問であるときの最小時刻}。気分的にはSRM 502 500pt: TheProgrammingContestDivOneみたいな。計算量O(N^2)。
実は貪欲でもよくて、これだとソートがボトルネックでO(N*logN)。

感想

区間スケジューリングっぽく貪欲で解くと思ってWAを連発した。結果的に貪欲でも解けるけどDP解の方が今見ると自然な気がする。

#include <cstdio>
#include <algorithm>
using namespace std;

int N;
int as[1009];
int bs[1009];
int dp[1009][1009];

int solve(){
	for(int i=0; i<N; i++)for(int j=0; j<N-1; j++){
		if(bs[j] > bs[j+1]){
			swap(bs[j], bs[j+1]);
			swap(as[j], as[j+1]);
		}
	}
	for(int i=0; i<=N; i++)for(int j=0; j<=N; j++) dp[i][j] = 1<<29;
	dp[0][0] = 0;
	for(int i=0; i<N; i++)for(int j=0; j<N; j++)if(dp[i][j] < (1<<29)){
		dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
		if(dp[i][j] + as[i] <= bs[i]){
			dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + as[i]);
		}
	}
	for(int i=N; i>=0; i--)if(dp[N][i] < (1<<29)) return i;
	return 0;
}

int main(){
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d%d",as+i,bs+i);
	}
	printf("%d\n",solve());
	return 0;
}