程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj3174【TJOI2013】拯救小矮人

bzoj3174【TJOI2013】拯救小矮人

編輯:C++入門知識

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

樣例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

感性地理解一下,a[i]+b[i]較大的小矮人逃跑的能力更強,所以我們要先讓a[i]+b[i]小的人盡可能先逃跑。於是可以想到按a[i]+b[i]從小到大排序,然後貪心計算。但這個貪心顯然是有問題的,所以我們考慮用DP解決貪心的不足。

貪心的不足之處在於當前的小矮人的a[i]還會對後面的小矮人產生影響,所以我們可以令f[i]表示逃跑了i個小矮人剩余a[i]和的最大值。在更新f數組的同時也就計算出了答案。

注意:f數組要逆向更新。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
using namespace std;
int n,h,ans,f[maxn];
struct data{int x,y;}a[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline bool cmp(data a,data b)
{
	return a.x+a.y=h) f[j+1]=max(f[j+1],f[j]-a[i].x);
		if (f[ans+1]>=0) ans++;
	}
	printf("%d\n",ans);
	return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved