題目描述?Description

不知為什么，yh的女朋友們都掉入了一個(gè)深度為h的天坑。由于天坑太深，yh的女朋友們無法爬出去，于是她們決定用搭人梯的方式脫困。我們知道yh的每位女朋友從腳到肩膀的高度ai，以及肩膀到伸直手臂的距離bi。由k個(gè)人搭成的人梯的高度為a1+a2+…+ak+bk;當(dāng)人梯高度大于等于h時(shí)，第k個(gè)人就可以爬出天坑，并再也不進(jìn)來。你能幫助他的女朋友們安排一個(gè)方案，使得最多的女朋友能爬出天坑嗎？

輸入描述?Input Description

第一行一個(gè)整數(shù)n，表示有n個(gè)女朋友掉進(jìn)坑里

第2行到第n+1行，每行兩個(gè)整數(shù)，表示女朋友從腳到肩膀的距離ai和從肩膀到伸直手臂的距離bi。

第n+2行為一個(gè)整數(shù)h，表示天坑深度為h。

輸出描述?Output Description

輸出一行，一個(gè)整數(shù)，表示最多能爬出天坑的女朋友的數(shù)量

樣例輸入?Sample Input

2

20?10

5?5

35

樣例輸出?Sample Output

1

數(shù)據(jù)范圍及提示?Data Size & Hint

對于40%數(shù)據(jù)，n≤100

對于100%數(shù)據(jù)，n≤2000，ai，bi，h≤100000

代碼:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[4001],n,h,ans;
struct node
{int ax,ay;
}a[2001];
bool cmp(const node&x,const node&y)
{return x.ax+x.ay<y.ax+y.ay;
}
int main()
{int i,j;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d%d",&a[i].ax,&a[i].ay);scanf("%d",&h);memset(f,-1,sizeof(f));f[0]=0;for(i=1;i<=n;i++)f[0]+=a[i].ax;sort(a+1,a+n+1,cmp);for(i=1;i<=n;i++)for(j=ans;j>=0;j--){if(f[j]+a[i].ay>=h)f[j+1]=max(f[j+1],f[j]-a[i].ax);if(f[ans+1]>=0) ans++;}printf("%d",ans);return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/jyhywh/p/6067246.html

總結(jié)

以上是生活随笔為你收集整理的codevs 2075 yh女朋友的危机的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。