DP + 单调队列
首先证明得到,高度最高的方案同时也是底部长度最小的方案。
sum[i]为1 - i的前缀和,f[i]代表考虑i - n使得底最小的底部宽度。
递推式 F[i]=min(sum[j-1]-sum[i-1]) j>i 且 sum[j-1]-sum[i-1]>=F[j] 易得在满足的条件下j当然是越小越好了嘛 而这样得出的方程又满足一定的单调性 这样调整之后队首就是我们要的答案啦
又对于转移条件 f[j]<=sum[j−1]−sum[i−1]。
#include <bits/stdc++.h> //#include <unordered_map> using namespace std; typedef long long ll; #define N (100010) #define maxn (N + 10) const ll mod = 998244353; const ll INF = (1e18) + 10; int sum[maxn], dp[maxn], q[maxn], h[maxn]; int main(){ int n;scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&sum[i]);sum[i] += sum[i - 1]; } int head = 0, tail = 0; q[head] = n + 1;sum[n + 1] = sum[n]; for(int i = n;i >= 1;i--){ while(tail < head && sum[i - 1] <= sum[q[tail + 1] - 1] - dp[q[tail + 1]]){ tail++; } dp[i] = sum[q[tail] - 1] - sum[i - 1]; h[i] = h[q[tail]] + 1; while(tail < head && sum[i - 1] - dp[i] >= sum[q[head] - 1] - dp[q[head]]){ head--; } q[++head] = i; } printf("%d\n",h[1]); return 0; }