80pts

算法分析

模拟，找到最高层，从下往上一层层消除，遇到不能连续消除的，就计数一次。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int main()
{
    int n;
    cin>>n;
    int maxv=0;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
        maxv=max(maxv,d[i]);
    }
    int ans=0;
    for(int i=1;i<=maxv;i++) //枚举高度
    {
        for(int j=1;j<=n+1;j++) //枚举是否当前层可以用上一次的操作
        {
            if(d[j]<i&&d[j-1]>=i) //j前面是有操作的且j不需要操作
            {
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

100pts

算法分析

通过对于区间的操作，我们可以容易想到将原来的序列做差分序列，这样对于每个区间的操作就相当于是对差分序列中选择两个数进行操作，

令原来的序列是$d_0,d_1,d_2...d_n,d_{n+1}$

差分序列是 $b_0=d_0,b_1=d_1-d_0...b_{n+1}=d_{n+1}-d_n$

那么原序列等于0，等价于然$b_0,b_1...b_n$全部变成0

对于$b_i > 0$,我们至少需要$\sum_{i=1}^{n} b_i$次操作才可以清零，

$d_{n+1}=b_0+b_1+b_2...b_{n+1}=0$ 当我们从前往后找到第一个大于0的数，由对称结构，一定可以在某个位置找到小于0的数，假设操作的区间是$[l,r]$,那么$b[l]-=1,b[r+1]+=1$,就是一组对称结构。

易得

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i];
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int b=d[i]-d[i-1]; //差分
        if(b>0) //至少需要b次操作
        {
            res+=b;
        }
    }
    cout<<res;
    return 0;
}