Luogu

BZOJ

分析

贪心 + $\mathrm{DP}$ 。

首先把所有小矮人按 $a+b$ 从小到大排序,这样子可以保证如果 $x$ 比 $y$ 先走,那么 $x$ 在序列中在 $y$ 的前面。

然后考虑 $\mathrm{DP}$ 。设 $f[i][j]$ 表示前 $i$ 个人走了 $j$ 个的最大高度。显然边界为 $f[0][0]=0$ 。

转移的话,考虑 $i$ 走不走。

  • 如果不走的话,用 $f[i-1][j]$ 来更新 $f[i][j]$ 。
  • 如果走的话,用 $f[i-1][j]$ 来更新 $f[i][j+1]$ 。

注意走是有条件的: $f[i-1][j]+s[i+1]+a[i]+b[i]\geq H$ 。这里的 $s$ 表示 $a$ 的后缀和。

这个条件应该比较容易理解,就是后面的全部堆起来,加上前面的人,再加上自己的高度能否出去。

答案就是最大的使得 $f[n][i]$ 被更新过的 $i$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int s[N],f[N][N];
struct node { int a,b; } a[N];
bool operator <(node a,node b) { return a.a+a.b<b.a+b.b; }

int main() {
    int n=read();
    for (re int i=1;i<=n;++i) a[i].a=read(),a[i].b=read();
    int h=read();
    
    sort(a+1,a+n+1);
    for (re int i=n;i;--i) s[i]=s[i+1]+a[i].a;
    
    memset(f,0xc0,sizeof(f)); f[0][0]=0;
    for (re int i=1;i<=n;++i)
        for (re int j=0;j<i;++j) {
            chkmax(f[i][j],f[i-1][j]+a[i].a);
            if (f[i-1][j]+s[i+1]+a[i].a+a[i].b>=h) chkmax(f[i][j+1],f[i-1][j]);
        }

    for (re int i=n;~i;--i)
        if (f[n][i]>=0) { printf("%d\n",i); break; }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 15 PM