BZOJ3174 [TJOI2013]拯救小矮人

2015.01.20 08:58 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

令第 $i$ 个小矮人逃跑能力为 $a_i + b_i$ 。那么对于两个小矮人,先令逃跑能力更小的矮人逃跑更优。于是按照逃跑能力排序即可得到矮人们的逃跑顺序。在这一基础上直接进行 DP 即可。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 2005

struct data
{
    int a, b;
    bool operator <(const data &x) const
    {
        return a + b < x.a + x.b;
    }
};

int n, h, ans, f[N]; data a[N];

int main()
{
    cin >> n;
    memset(f, 0xff, sizeof f); f[0] = 0;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].a >> a[i].b, f[0] += a[i].a;
    sort(a + 1, a + n + 1);
    cin >> h;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = ans; j >= 0; --j)
            if (a[i].b + f[j] >= h)
                f[j + 1] = max(f[j + 1], f[j] - a[i].a);
        ans += (f[ans + 1] >= 0);
    }
    cout << ans << endl;
}