常州模拟赛d4t2 陶陶摘苹果
题目描述
陶陶家的院子里有一棵苹果树,每到秋天树上就会结出 n 个苹果。苹果成熟的时候,陶陶就会
跑去摘苹果。
陶陶的手不能弯 (他仅能把手伸直),当且仅当陶陶达到的高度与苹果的高度相等的时候,陶陶
才能摘到苹果。
好在陶陶有 m 个板凳,每个板凳的高度可以在区间 [l i ,r i ] 之间上下移动 (即可以随时变为该区
间中任何一个值)。当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。
但是搬板凳对陶陶来说是一件费力的事情,所以他只能选择 k 个板凳来使用。
现在已知 n 个苹果到地面的高度,m 个板凳的高度区间,陶陶能选择的板凳数 k,以及陶陶把
手伸直能达到的高度 h,请帮陶陶算一下她最多能够摘到的苹果的数目。假设她碰到苹果,苹果就
会掉下来。
输入输出格式
输入格式:
第一行四个正整数 n,m,h,k,表示苹果的数量、板凳的数量、陶陶把手伸直能达到的高度和陶
陶最多选择的板凳数量。
第一行包含 n 个正整数,第 i 个正整数 a i 表示第 i 个苹果到地面的高度,两个相邻的整数之间
用一个空格隔开。
接下来 m 行,每行两个非负整数 l i ,r i ,表示第 i 个板凳的高度区间。
输出格式:
一个数,表示最多摘到的苹果数。
输入输出样例
10 5 110 3
100 200 150 140 129 134 167 198 200 111
0 30
20 40
90 100
100 110
50 60
7
说明
对于 30% 的数据:m ≤ 10,a i ,h ≤ 1000,l i ≤ r i ≤ 1000;
对于 100% 的数据:k ≤ m ≤ 200,n ≤ 1000000,a i ,h ≤ 1000000,l i ≤ r i ≤ 1000000。
分析:这道题显然是个dp题.
数据范围已经给了很明显的提示,我们要记录二维状态,一维是k,其它的只有m可以记录,那么状态f[i][j]表示选了i个板凳,这次选的是第j个,f[i][j] = max{f[i-1][p] + s}.
但是每个板凳只能选一次,我们要怎么处理呢?很简单,p枚举到j-1就好了.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<map>
#include<algorithm> using namespace std; const int maxn = ; int n, m, h, k,a[maxn + ],ans,num[maxn + ],sum[maxn + ],f[][],anss; struct node
{
int l, r;
}e[maxn]; bool cmp(node a, node b)
{
return a.r < b.r;
} int main()
{
scanf("%d%d%d%d", &n, &m, &h, &k);
for (int i = ; i <= n; i++)
{
scanf("%d", &a[i]);
if (a[i] == h)
ans++;
else
num[a[i]]++;
}
for (int i = ; i <= maxn; i++)
sum[i] = sum[i - ] + num[i];
for (int i = ; i <= m; i++)
{
scanf("%d%d", &e[i].l, &e[i].r);
e[i].l += h;
e[i].r += h;
}
sort(e + , e + + m, cmp);
for (int i = ; i <= k; i++)
for (int j = ; j <= m; j++)
for (int p = ; p < j; p++)
{
int t = sum[e[j].r] - sum[max(e[j].l - , e[p].r)];
f[i][j] = max(f[i][j], f[i - ][p] + t);
}
for (int i = ; i <= m; i++)
anss = max(f[k][i],anss);
printf("%d\n", anss + ans);
return ;
}
最新文章
- 爬虫初探(2)之requests
- C#编写简单的聊天程序
- Android 用代码设置Shape,corners,Gradient
- [转]or cad drc 错误
- js获取项目根路径
- 解释一下,在你往浏览器中输入一个URL后都发生了什么,要尽可能详细
- protoc-gen-lua
- leetcode -- Largest Rectangle in Histogram TODO O(N)
- jquery之杂记
- Goldbach&#39;s Conjecture(哥德巴赫猜想)
- SQLServer 查看SQL语句的执行时间
- sdk安装
- 协议形式化分析Scyther 资料整理
- Flask上下文管理源码--亲自解析一下
- android 图形图像
- Expressions versus statements in JavaScript
- Python 多进程基本语法
- 数据库-->;记录操作
- 在Java中,以下关于方法重载和方法重写描述正确的是?
- Windows下sbt安装配置
热门文章
- 第14周翻译:SQL Server的阶梯安全级别2
- codevs 3054 高精度练习-文件操作
- 导致实例逐出的五大问题 (文档 ID 1526186.1)
- 根据HTML语义化编码
- DirectX9(翻译):介绍
- 浅谈js的sort()方法
- tomcat常用的优化和配置
- 【DB_MySQL】查询语句中各子句的执行顺序
- 条款37:绝不重新定义继承而来的缺省参数值(Never redefine a function&#39;s inherited default parameter value)
- LeetCode(116) Populating Next Right Pointers in Each Node