「BZOJ3174」[TJOI2013] 拯救小矮人
Description
一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的 肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我 们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+….+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一 旦一个矮人逃跑了，他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑， 问最多可以使多少个小矮人逃跑。
Input
第一行一个整数N， 表示矮人的个数，接下来N行每一行两个整数Ai和Bi，最后一行是H。（Ai，Bi，H<=10^5）
Output
一个整数表示对多可以逃跑多少小矮人
Sample Input
样例12
20 10
5 5
30
20 10
5 5
30
样例2
2
20 10
5 5
35
Sample Output
样例1
2样例2
1
2样例2
1
HINT
数据范围
30%的数据 N<=200
100%的数据 N<=2000
题解
考虑相邻的a和b
若a.a+a.b<b.a+b.b则b应该在a之后逃跑
大概这样理解
就是如果只能通过一个，那么我无论怎么放都一样（后面是dp）
如果可能通过俩，那么显然要把逃跑能力强的放在后面
如果可能通过俩，那么显然要把逃跑能力强的放在后面
然后dp一下
f[i]表示逃跑i个人后剩下的人梯最高的高度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define ll long long #define mod 1000000007 using namespace std; int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x; } struct data{ int a,b; }a[2005]; int n,m; int f[2005]; bool operator<(data a,data b) { return a.a+a.b<b.a+b.b; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(); memset(f,-1,sizeof(f)); f[0]=0; for(int i=1;i<=n;i++) f[0]+=a[i].a; sort(a+1,a+n+1); m=read(); int h=0; for(int i=1;i<=n;i++) for(int j=h;j>=0;j--) { if(f[j]+a[i].b>=m) f[j+1]=max(f[j+1],f[j]-a[i].a); if(f[h+1]>=0)h++; } printf("%d",h); return 0; } |
Subscribe
计数器 9856794
OI 课件=>
OI 课件=>