动态规划
令f(n)=E(n), 则f(n+1) = 2f(n) - H(n+1) >= 0,所以 f(n) = Math.ceil((f(n+1) + H(n+1))/2)
最后用递推从n -> 0 即可求出f(0),也就是E(0)
时间复杂度分析:O(n)
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(bf.readLine());
String[] high = bf.readLine().split(" ");
int energy = 0;
for (int i = high.length - 1; i >= 0; i--) {
if ((Integer.parseInt(high[i]) + energy) % 2 == 1) {
energy = (Integer.parseInt(high[i]) + energy) / 2 + 1;
} else {
energy = (Integer.parseInt(high[i]) + energy) / 2;
}
}
System.out.println(energy);
}
}