Home => ProblemSet => 200.1-58:粉刷木板
1954: 200.1-58:粉刷木板
Time Limit: 1 Sec Memory Limit: 128 MB Submit: 0 Solved: 0[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
小V将家里的n块木板排列在一起，木板编号1,2...n。每块木板宽1米，高ai米。
小V用宽1米的刷子沿木板水平或者垂直方向粉刷木板。
木板之间无空隙，只刷木板的一面，可以多次反复刷木板的某一个区域，刷子带有存放油漆的设备可以随时加油漆。
刷子离开木板算一次。
问小V至少要刷多少次才能刷完栅栏。
小V用宽1米的刷子沿木板水平或者垂直方向粉刷木板。
木板之间无空隙，只刷木板的一面，可以多次反复刷木板的某一个区域，刷子带有存放油漆的设备可以随时加油漆。
刷子离开木板算一次。
问小V至少要刷多少次才能刷完栅栏。
Input
第一行一个整数n(1 <= n <= 5000)，表示栅栏木板的数量
第二行n个空格分隔的整数a1,a2...an(1 <= ai <= 109)
第二行n个空格分隔的整数a1,a2...an(1 <= ai <= 109)
Output
一个整数，表示刷满整个栅栏所需的最少粉刷次数。
Sample Input Copy
5
2 2 1 2 1
Sample Output Copy
3
HINT
样例一解释：
第一个样例，至少要粉刷三次：第一次沿着所有木板的水平方向在高度1上刷。
第二次在高度2上横向刷第一块和第二块木板，第三次(横向或竖向都可以)刷完第四块木板。
样例二：
输入：
2
2 2
输出：
2
样例二解释：
至少两次刷完，可以是横向的两次，也可以是竖向的两次。
34%的数据,n <= 30;
100%的数据,1 <= n <= 5000, 1 <= ai <= 10^9
其中10%的数据，所有ai都相等；
8%的数据，任意两个ai最多相差1；
8%的数据，ai单调不减；
4%的数据，ai单调不增。
第一个样例，至少要粉刷三次：第一次沿着所有木板的水平方向在高度1上刷。
第二次在高度2上横向刷第一块和第二块木板，第三次(横向或竖向都可以)刷完第四块木板。
样例二：
输入：
2
2 2
输出：
2
样例二解释：
至少两次刷完，可以是横向的两次，也可以是竖向的两次。
34%的数据,n <= 30;
100%的数据,1 <= n <= 5000, 1 <= ai <= 10^9
其中10%的数据，所有ai都相等；
8%的数据，任意两个ai最多相差1；
8%的数据，ai单调不减；
4%的数据，ai单调不增。