简答题
偏难
#23313
铺设道路 【问题描述】 春春是一名道路工程师,负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一…
铺设道路
【问题描述】
春春是一名道路工程师,负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di 。
春春每天可以选择一段连续区间 [L, R] ,填充这段区间中的每块区域,让其下陷深度减少 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0 。
【输入格式】
输入文件名为 road.in。
输入文件包含两行,第一行包含一个整数 n,表示道路的长度。
第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。
【输出格式】
输出文件名为 road.out。
输出文件仅包含一个整数,即最少需要多少天才能完成任务。
【输入输出样例 1】

【样例解释】
一种可行的最佳方案是,依次选择:
[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 。
答案与解析
正确答案:<p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">#define inf 0x3f3f3f3f</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">int ans,d[100001],N;</p><p style="text-align: left;">int partition1(int left, int right) //分治(实现这一片区域的操作)</p><p style="text-align: left;">{ int sum1=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(left>=right) //当不能再分时返回</p><p style="text-align: left;"><span style="white-space:pre"> </span>{ </p><p style="text-align: left;"><span style="white-space:pre"> </span>if(left==right) //如果区域是单个数</p><p style="text-align: left;"><span style="white-space:pre"> </span>{ int t=d[left];</p><p style="text-align: left;"><span style="white-space:pre"> </span>d[left]=0; //清0</p><p style="text-align: left;"><span style="white-space:pre"> </span>return t; //直接返回里面的值(它里面的值代表这个单个区域需要的天数)</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>else</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>} </p><p style="text-align: left;"><span style="white-space:pre"> </span> int min1=inf,l=left;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for (int i=left; i<=right;i++) //求出这片区域的最小值</p><p style="text-align: left;"><span style="white-space:pre"> </span> min1=min(d[i],min1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum1+=min1;//先把最小值加上</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=left; i<=right; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{ d[i]-=min1; //每个都减去最小值</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(d[i]==0&&d[i-1]!=0) //如果遇到0分界线</p><p style="text-align: left;"> {</p><p style="text-align: left;"><span style="white-space:pre"> </span> sum1+=partition1(l,i-1);//把之前的区域分治</p><p style="text-align: left;"><span style="white-space:pre"> </span> }</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(d[i]!=0&&d[i-1]==0) l=i;//如果在0之后遇到新的左端点,更新</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(d[right]!=0)//不要忘掉最后一块区域</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum1+=partition1(l,right);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return sum1;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>//freopen("in.txt","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin>>N;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=N;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> cin>>d[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span> ans=partition1(1,N);</p><p style="text-align: left;"><span style="white-space:pre"> </span> cout<<ans;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;"> } </p>
这道题暂未补解析。