原题链接

ACwing

思路

首先，原问题的解显然具有单调性——如果一个解比最优解大，那么其一定也是可行的，因为其在每一个点减少的更少，增加的更多。显然，本题可以使用二分判定一个解，不过该做法因为数据大小限制，不可行（在check解的过程中会溢出）。

那么，我们可以直接推出最优解吗？简单倒推，在最后一个站点，为了通过的最小能量值实际上就是该站点能量的一半（向上取整）；那么倒数第二个站点，为了通过的最小能量值就是通过当前站点并且可以通过下一个站点：。根据该式子倒推即可。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int N = 100000 +10;
typedef long long ll;
int H[N];
int dp[N];

int main(){
    int n;
    cin>>n;
    int ans = 0;
    memset(dp, 0, sizeof dp);
    memset(H, 0, sizeof H);
    for(int i=1;i<=n;i++){
        cin>>H[i];
    }
    
    for(int i=n;i>=1;i--){
        dp[i] = (H[i]+dp[i+1]+1)/2;
    }
    cout<<dp[1]<<endl;
    return 0;
}