嗯...

 

题目链接：https://www.luogu.org/problem/P5019

 

首先简化一下题意：

给定一个长为N的数组，每次操作可以选择一个区间减去1，问最少多少次操作可以将数组中的数全变成0 N≤100000

 

思路：

首先对于第一个数字d_1我们至少需要在上面花d_i次，然后考虑每一个d_i，对于它比上一个数字小（或等于）的那一部分，

我们可以在对上一个数字操作时一块操作。如果d_i > d_i - 1，也就是说它比上一个数大，那么我们就必须多进行d_i - d_i - 1次操作。

很明显，数与数之间会有差，而差会造成一些区间问题，所以这道题的正解是差分...

我们用b数组维护差分，然后将大于0的差分数组加到ans中即可。

 

AC代码：

1 #include
      
        2 #include
       
         3  4 using namespace std; 5  6 int ans, d[100005], b; 7  8 int main(){ 9     int n;10     scanf("%d", &n);11     for(int i = 1; i <= n; i++){12         scanf("%d", &d[i]);13         b = d[i] - d[i - 1];14         if(b > 0) ans += b;15     }16     printf("%d", ans);17     return 0;18 }19