BZOJ3174 [Tjoi2013]拯救小矮人

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

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

样例1

2
20 10
5 5
30

样例2
2
20 10
5 5
35

Sample Output

样例1
2

样例2
1

HINT

 

数据范围

30%的数据 N<=200

100%的数据 N<=2000

 
 

正解:贪心+DP

解题报告:

   这道题长得就像一道贪心题QAQ

  关键是怎么贪…

  考虑肯定是长得高而且手长的对别人的依赖要小一些,也就是说需要的别人提供的高度少,那么显然可以靠后逃生。不妨定义每个人的逃生能力为高度+手长,那么排序之后,就可以考虑一个最优的逃生序列。

  对于每个人更新一下,他是第几个逃生的最优情况。

  $f[i]$表示逃了$i$个人之后的剩余最大高度,不断更新即可。

 

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 100011;
int n,H,top;
int f[MAXN];//f[i]表示跑掉i个人之后的最高高度
struct node{ int A,B,C; }a[MAXN];
inline bool cmp(node q,node qq){ return q.C<qq.C; }
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}

inline void work(){
	n=getint(); for(int i=1;i<=n;i++) a[i].A=getint(),a[i].B=getint(),a[i].C=a[i].A+a[i].B;
	H=getint();
	sort(a+1,a+n+1,cmp);//逃生能力从小到大排序
	memset(f,-1,sizeof(f)); f[0]=0; top=0;
	for(int i=1;i<=n;i++) f[0]+=a[i].A;
	for(int i=1;i<=n;i++) {
		for(int j=top;j>=0;j--) {
			if(f[j]+a[i].B>=H) f[j+1]=max(f[j+1],f[j]-a[i].A);
			if(f[top+1]>=0) top++;
		}
	}
	printf("%d",top);
}

int main()
{
    work();
    return 0;
}

  

原文地址:https://www.cnblogs.com/ljh2000-jump/p/6288971.html