AtCoder Beginner Contest 116 C题【题意：可以在任意区间【L,R】上加1，求通过最少加1次数得到题目给定的区间】】{思维好题}

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

C - Grand Garden

In a flower bed, there are NN flowers, numbered 1,2,......,N1,2,......,N. Initially, the heights of all flowers are 00. You are given a sequence h={h1,h2,h3,......}h={h1,h2,h3,......} as input. You would like to change the height of Flower kk to hkhk for all kk (1≤k≤N)(1≤k≤N), by repeating the following "watering" operation:

Specify integers ll and rr. Increase the height of Flower xx by 11 for all xx such that l≤x≤rl≤x≤r.

Find the minimum number of watering operations required to satisfy the condition.

Constraints

1≤N≤1001≤N≤100
0≤hi≤1000≤hi≤100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

NNh1h1 h2h2 h3h3 ............ hNhN

Output

Print the minimum number of watering operations required to satisfy the condition.

Input

Output

Input

Output

题意：可以任意在区间【L,R】上加1，求通过最少次数得到题目给定的区间的值】

AC代码：

#include<bits/stdc++.h>using namespace std;#define int long long];signed main(){ ; int n; cin>>n; ;i<=n;i++) scanf("%lld",&arr[i]); ]; ;i<=n;i++){ if(i==n){ // 特判一下 ans+=max(arr[i],temp); }else{ if(arr[i]>=temp){ temp=arr[i]; }else{ ans+=abs(arr[i]-temp);// 需要减去多加的数 temp=arr[i]; } } } cout<<ans; ;}

代码2

#include<bits/stdc++.h>using namespace std;#define N 515155int arr[N];int main(){ int n; cin>>n; ; scanf(]); ){ cout<<arr[]; ; } ]; ;i<=n;i++){ scanf("%d",&arr[i]); if(i==n){ ans+=max(temp,arr[i]); break; } if(arr[i]<temp){ ans+=temp-arr[i]; temp=arr[i]; }else{ temp=arr[i]; } } cout<<ans; ;}