首页 > 代码库 > 洛谷P1969 积木大赛 数学
洛谷P1969 积木大赛 数学
洛谷P1969 积木大赛
题意: 对于n个积木 排成了一排 高度不同
每次可以使 L--R的区间积木减一,但不能使积木高度减至 0 以下 ,
求几次能够使得所有积木高度降为 0
数学
1、对于一段 上升、不下降序列,其较低的一定会在解决最高时候就解决掉
2、而这段区间还同时会解决掉下一段区间最小值 以下的那些积木
3、所以这段区间消耗值就是这段上升(不下降)序列的最大值减最小值
先写思路:
对于一段上升(不下降)区间,我们在搭最高层时可以把下面一起搭了
而如果这个区间开始下降,那么我们进入另一个区间,这个上升区间中
的最小值以下部分都可以在上个区间搭完,所以他的消耗就是本区间最大减最小(第一段减0)
复杂度O(n) 啦啦啦
1 #include <cstdio> 2 #include <cstring> 3 using namespace std ; 4 5 int n,ans,last ; 6 int h[100001] ; 7 8 int main() 9 { 10 scanf("%d",&n) ; 11 for(int i=1;i<=n;i++) 12 scanf("%d",&h[ i ]) ; 13 last = 0 ; 14 for(int i=1;i<=n;i++) 15 if( h[ i ] > h[ i+1 ]) 16 ans+=( h[ i ]-last ),last = h[ i+1 ] ; 17 printf("%d\n",ans) ; 18 return 0 ; 19 }
洛谷P1969 积木大赛 数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。