题目
输入输出样例 输入：
6
4 3 2 5 3 5
输出：
9
思路：
数组ans[i]表示铺平前i块所需要的最短天数 遍历所有土地： 两种情况： 当depth[i+1]<=depth[i]时，即，后面的坑的深度小于前面，则可以铺平前面时，一起把后面的铺平后边的区域（后面的趁着前边铺的时候铺平）。所以ans[i+1]=ans[i]. 当depth[i+1]>depth[i]时，即，后面的坑的深度大于前面，那么铺平后面的则需要，先铺平前边（ans[i]），再铺平后边比他前边那一个多出的部分（depth[i+1] - depth[i]）。所以ans[i+1]=ans[i]+(depth[i+1]-depth[i]).
代码
import java.util.Scanner
;
public class Main
{
public static void main
(String
[] args
) {
Scanner sc
=new Scanner
(System.in
);
int n
=sc.nextInt
();
int
[] depth
=new int
[n+1
];
int
[] ans
=new int
[n+1
];//铺平前i块，需要的最短天数
for (int i
= 1
; i
<= n
; i++
) {
depth
[i
]=sc.nextInt
();
}
ans
[1
]=depth
[1
];
for (int i
= 1
; i
< n
; i++
) {
if (depth
[i+1
]<=depth
[i
]){
ans
[i+1
]=ans
[i
];
}else
{
ans
[i+1
]=ans
[i
]+
(depth
[i+1
]-depth
[i
]);
}
}
System.out.println
(ans
[n
]);
}
}
