ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2263 The First Acceptance

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2263


解法


動的計画法(DP)で解くことができます。

int dp[何問目か][解いた数] = 経過時間
のような配列を用意してやればよいです。

ファーストアクセプトが他者に取られる時間順で前もってソートしておく必要があります。


ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define REP(i,x,n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)

static const int INF = (1 << 29);

struct Problem {
  int A,B;
  
  Problem(){}
  Problem(int a, int b):A(a),B(b){}
  
  bool operator < (const Problem &p) const {
    if(B == p.B) return A < p.A;
    else return B < p.B;
  }
};

int N;
int dp[1001][1001];
vector<Problem> problem;

int solve(){
  sort(problem.begin(), problem.end());
  rep(i,1001) rep(j,1001) dp[i][j] = INF;
  dp[0][0] = 0;
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      dp[i + 1][j] = dp[i][j];
    }
    for(int j = 0; j < N; j++){
      if(dp[i][j] == INF) continue;
      if(dp[i][j] + problem[i].A > problem[i].B) continue;
      dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + problem[i].A);
    }
  }
  
  int ans = 0;
  rep(i, N + 1) if(dp[N][i] != INF) ans = i;
  
  return ans;
}

int main(){
  cin >> N;
  rep(i,N){
    int a,b;
    cin >> a >> b;
    problem.push_back(Problem(a,b));
  }
  cout << solve() << endl;
  return 0;
}