儿童故事书,在线娱乐城,face gossip下载
一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯。即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人,我们知道他从脚到肩膀的高度ai,并且他的胳膊长度为bi。陷阱深度为h。如果我 们利用矮人1,矮人2,矮人3,。。。矮人k搭一个梯子,满足a1+a2+a3+....+ak+bk>=h,那么矮人k就可以离开陷阱逃跑了,一 旦一个矮人逃跑了,他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑, 问最多可以使多少个小矮人逃跑。
数据范围
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; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论