BZOJ3174:[TJOI2013]拯救小矮人(DP)
2024-09-21 17:31:50
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
样例2
1
HINT
数据范围
30%的数据 N<=200
100%的数据 N<=2000
Solution
证明戳这里吧
$f[i]$表示跑了$i$个人后剩下的能组成的人梯的最高高度
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (2009)
using namespace std; struct Node
{
int x,y;
bool operator < (const Node &a) const
{
return x+y<a.x+a.y;
}
}a[N];
int n,h,f[N],ans,sum; int main()
{
scanf("%d",&n);
for (int i=; i<=n; ++i)
scanf("%d%d",&a[i].x,&a[i].y),sum+=a[i].x;
scanf("%d",&h);
sort(a+,a+n+);
memset(f,-,sizeof(f));
f[]=sum;
for (int i=; i<=n; ++i)
for (int j=ans; j>=; --j)
{
if (f[j]+a[i].y>=h)
f[j+]=max(f[j+],f[j]-a[i].x);
if (f[ans+]>=) ans++;
}
printf("%d\n",ans);
}
最新文章
- Burpsuite+sqlmap批量扫描sql漏洞
- 【C语言入门教程】3.2 数据的输入 与 输出
- Python脚本模拟登录网页之CSDN篇
- Leetcode: Minimum Number of Arrows to Burst Balloons
- Educational Codeforces Round 14 E.Xor-sequences
- sql left join、right join、inner join
- 咏南CS插件开发框架也可BS方式部署
- paper 32 :svm参数优化的进展
- Unity3d纹理压缩格式表
- 配置文件struts2Struts2配置文件模块化包含(include)与action总结
- hdu 2665 Kth number_划分树
- 机器学习 —— 基础整理(四)特征提取之线性方法:主成分分析PCA、独立成分分析ICA、线性判别分析LDA
- UIKit视图动画的微扩展
- Windows Server Backup(2016) 备份
- 封装json输出
- 解决微信浏览器无法使用window.location.reload刷新页面
- Eclipse的各种查找,类的查找,方法查找快捷键
- :target方法实现切换
- Sprint会议计划
- Nginx 关键字详解
热门文章
- SQL Server 导入excel时“该值违反了该列的完整性约束”错误
- C# 实现将listview中已经显示的数据导出到Access 数据库
- Docker学习之Centos7下安装
- 设计模式之——外观or门面模式
- 使用 NamedScope 扩展 Ninject 的 InRequestScope
- 《JavaWeb从入门到改行》分页功能的实现
- python学习之老男孩python全栈第九期_day028知识点总结——面向对象进阶、hashlib
- Struts2 数据校验之四兄弟
- HDU P2089
- JavaScript函数与面向对象