P5019 铺设道路

admin

https://www.luogu.org/problemnew/show/P5019
题目描述
春春是一名道路工程师，负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 di。

春春每天可以选择一段连续区间 [L,R] ，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。

输入输出格式
输入格式：
输入文件包含两行，第一行包含一个整数 n，表示道路的长度。 第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i个整数为 di。

输出格式：
输出文件仅包含一个整数，即最少需要多少天才能完成任务。

输入输出样例
输入样例#1：
6   
4 3 2 5 3 5
输出样例#1：
9
说明
【样例解释】

一种可行的最佳方案是，依次选择： [1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于 30% 的数据，1 ≤ n ≤ 10 ；
对于 70% 的数据，1 ≤ n ≤ 1000；
对于 100% 的数据，1 ≤ n ≤ 100000 , 0 ≤ di ≤ 10000。

admin

注意看我的测试数据，程序代码如下：

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=110000;
   
4. int a[mm],n;
   
5. int slove(int l,int r) ///l到r要花少时间
   
6. {
   
7.     if (l>r) return 0;
   
8.     if (l==r) return a[l];
   
9.     int minx=0X3F3F3F3F,p0=0,i;
   
10.     for (i=l;i<=r;i++) if (a[i]<minx) {minx=a[i];p0=i;}
    
11.     for (i=l;i<=r;i++) a[i]-=minx;
    
12.     return slove(l,p0-1)+slove(p0+1,r)+minx;
    
13. }
    
14. int main()
    
15. {
    
16.     cin>>n;
    
17.     for (int i=1;i<=n;i++) cin>>a[i];
    
18.     cout<<slove(1,n);
    
19.     return 0;
    
20. }
    

复制代码

admin

我先用第一种方法，就是硬模拟统计，打了个草稿，简单设计了一下测试数据和程序框架，就开始编程了，因为这个对于我来说，程序代码复杂度不高。

admin

这个题出的很好，虽然有重复的嫌疑，我以前也说过一个和这个类似的浇花的题目，但是这个提确实很训练思维。
首先看到这个题目，不假思索地话可以考虑用硬模拟的方法，找到最小值，大家都填满最小值，最小值变成了0，将原来的序列分割成两个序列，分别递归计算。这个的证明简直是无需的，但是编码你会很快做出来吗？
再分析以下：若是右边的数字何和左边相等，是不是完全没有存在的必要？那要是大呢，小呢？那么是不是可以想到一个类似找最长连续下降的做法？？是不是有点像数列分段那个题？