首页 > 试题广场 >

升级蓄水池

[编程题]升级蓄水池
  • 热度指数：1156 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
在米兔生活的二维世界中，建造蓄水池非常简单。
一个蓄水池可以用n个坐标轴上的非负整数表示，代表区间为【0-n】范围内宽度为1的墙壁的高度。
如下图1，黑色部分是墙壁，墙壁的高度是[0,1,0,2,1,0,1,3,2,1,2,1] ，蓝色部分是蓄水的面积，可以看出蓄水池最大蓄水容量是6。
现在米兔想通过增加某些墙壁的高度对蓄水池扩容，但是经费有限，最多只能增加最多m的高度，增加高度只能在【0-n】范围内，高度为0的区域也是可以增加的，为了追求最大的性价比，米兔想要找到一种最优方案，使扩容后蓄水池的容量最大，你能帮帮他么？
提示：
对于样例，图2，图3，是样例可能的两种扩容方案，显然图2是比图3更优的方案


输入描述:
第一行为一个数字n
接下来n行，每行一个数字，代表n个墙壁的高度
最后一行为一个数字m


输出描述:
一个数字，表示扩容之后蓄水池能达到的最大容量
示例1

输入

12
0
1
0
2
1
0
1
3
2
1
2
1
2

输出

12

备注:
关于题目数据范围
20%的数据， n<10,m<10,蓄水池最大高度小于10
50%的数据， n<100,m<100,蓄水池最大高度小于100
100%的数据， n<1000,m<1000,蓄水池最大高度小于1000
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-28 22:01:22
解题思路 这是一道动态规划问题，主要思路如下： 问题分析： 给定 个位置的墙壁高度 可以增加总共 个单位的高度 需要找到最优的扩容方案 解决方案： 计算左右两侧的单调递增序列 计算每个区间的剩余空间 动态规划处理高度分配 关键步骤： 维护前缀和数组 计算每个区间的最大容量 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 贪心 动态规划 小米集团 模拟 测试工程师 2019 Java工程师
来自：小米2019秋招软件开...
上传者：小小
难度：
6条回答 6582浏览

热门推荐

通过挑战的用户

查看代码

相关试题

升级蓄水池

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号