CODE FESTIVAL 2017 Final D - Zabuton

問題ページ
D - Zabuton

学び

最適な並べ方について考える発想がなかった(求められると思わなかった)
2要素を並べてどちらを前にするべきかを数式で書くとh+pが出て来る
最適な並べ方について考えてそれを満たすような数列を考える hを状態に持つDPしか思い浮かばなかった DPの取り方を頭に入れておく

解法

h+pで昇順にソートした後DPをする
dp[i人目][j人選んだ] = (最小の高さ)として
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + v[i][2]) と遷移する

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[5010][5010];
signed main(void)
{
  int n;
  cin >> n;
  VVI v;
  REP(i, n) {
    int h, p;
    cin >> h >> p;
    v.PB({h+p, h, p});
  }
  sort(ALL(v));

  REP(i, n) REP(j, n+1) dp[i][j] = INF;
  dp[0][0] = 0;
  dp[0][1] = v[0][2];
  FOR(i, 1, n) {
    dp[i][0] = 0;
    FOR(j, 1, n+1) {
      if(dp[i-1][j-1] <= v[i][1]) dp[i][j] = min(dp[i-1][j], dp[i-1][j-1] + v[i][2]);
      else dp[i][j] = dp[i-1][j];
    }
  }

  int ret = 0;
  REP(i, n+1) if(dp[n-1][i] < INF) ret = i;
  cout << ret << endl;

  return 0;
}