洛谷 P5019 铺设道路

有一条长度为n的道路，可以看作是n块首尾相连的区域，一开始，第i块区域下陷深度为d[i]。每天可以选择一段连续区间[L,R],填充这段区间中的每块区域，让其下陷深度减少1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为零。求所需的最少天数。原题

借鉴的思路

#include<iostream>
using namespace std;
int longth;
int road[100005] = { 0 };
int main()
{
 int days = 0;
 cin >> longth;
 for (int i = 1; i <= longth; i++)
 {
  cin >> road[i];
 }//输入每一段的下陷深度
 for (int i = 1; i <= longth; i++)
    //注意循环的起始点，因为if语句里总是将当前项与前一项比较，所以定义road[0] = 0是为了使得road[1]被纳入计算days的范围
 {
  if (road[i] > road[i - 1])
        //进行比较，如果后面的坑比前面的深，则在填较深的那个的时候与它相邻的那个总会捎带一起填平，所以就不需要去专门填较浅的坑
  {
   days = road[i] - road[i - 1]+days;
            //这里是计算出大坑相对于小坑多花的天数，如果向后遍历一直是小坑，则不需要计入天数，因为小坑总是会被与它相邻的大坑捎带填平

  }
 }
 cout << days << endl;
 return 0;
}

我的思路

不管采用什么样的顺序，最深的坑总是最花费最多的天数才能被填满，所以每一次总是当前从最深的坑下手，然后以当前最深的坑为起点，向前向后遍历寻找符合要求的最长填坑区间，找出区间后将对应区间的坑深度减一。思路是没有漏洞的，但是洛谷提交后三个点会超时，在千方百计优化以后，仍然会超时，是思路及本身时间复杂度的问题。就是想不到题解的思路，只有七十分，果然模拟不能AC这道题。