AcWing 507. 积木大赛    原题链接    中等

作者： 作者的头像   未名湖畔的梦 ,  2021-02-14 11:35:05 ,  所有人可见 ,  阅读 467

5


填坑时将小坑带着一起填
问题转化为叠积木,
我们需要的是每一部分（有的地方是平的,不用填）的最大值即可
若a[i]>a[i-1],计数器sum+=a[i]-a[i-1];
等价于找每个=块的最大高度

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;

int n,a[MAXN],ans;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)  scanf("%d",a+i);
    for(int i = 2; i <= n; i++) 
      if(a[i] >a[i-1] ) 
        ans += a[i]- a[i-1] ;
    cout<<ans+a[1]; 
    return 0;
}

eg :一模一样的题目就是换了个外套，读者也可以试着写写

4 评论

用户头像
玛卡巴卡呀   2021-04-07 17:12         踩      回复

为什么每一次都要判断相邻的两个块的高度呢？不可以跨越的填坑嘛

用户头像
未名湖畔的梦   2021-04-07 20:38         踩      回复

emmm,你可以想象一下填坑嘛:

                     j 
i 1 2 3 4 5 6 7 8 9  1 
  - -             -  2 
  - - - -     - - -  3 
  - - - - - - - - -  4

(图比较简陋，用学校的虚拟机不能拍照，将就着看吧)

比如这样的积木你要怎么填？？

1.将 i = 1 这列给全填了， 再 i = 2 这列给填了 …（就相当于按顺序填满,我们可以发现这很明显操作的次数就是列数）

2.我们可以将最底下的这行给填满（即填 j = 4这行，总共要 1次）， 再填 j = 3 这行， 但是你会发现中间断掉了，所以呢？？ 你应该是把 i = 1 -> i = 4这段填起来，再填 i = 7 -> i = 9这段 ，总共要2次；再第j = 2 这行，已此类推…

简单来说就是从最底下一层一层的往上堆。

综上方法2： 我们可以发现如果是单调递增的地方（当然不是严格的递增，相等也行）就加上这个高度差，单调递减的地方就说明前面已经堆过了，没必要继续堆，直接忽视

用户头像
未名湖畔的梦   2021-04-07 20:38    回复了 未名湖畔的梦 的评论         踩      回复

这图里面-代表要填的积木

用户头像
玛卡巴卡呀   2021-04-07 20:45    回复了 未名湖畔的梦 的评论         踩      回复

好像理解了一些了，多谢多谢