CF1918D 题解
Register_int
2024-01-31 00:46:31
答案由两部分组成，一部分为加和，另一部分为 $\max$。假设我们当前已经确定答案不超过 $x$，那么有：
- 两个点间的最大间隔不超过 $x$。
- 点权之和不超过 $x$。
不妨用前者来约束后者。加入两个虚点 $a_0=a_{n+1}=0$，设 $dp_i$ 表示考虑前 $i$ 个位置，选了第 $i$ 个位置，且最大间隔不超过 $x$ 的最小价值。容易得到转移：
$$dp_i=a_i+\min_{s_{i-1}-s_j\le x}dp_j$$
其中 $s$ 为前缀和数组。显然每次可转移到 $i$ 的区间左右端点都单增，所以可以单调队列优化至线性。
此时 $dp_{n+1}$ 即为答案，若 $dp_{n+1}\le x$，则表示答案可以 $\le x$。二分答案即可，时间复杂度 $O(n\log nV)$。
# AC 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int T, n; ll a[MAXN], s[MAXN], dp[MAXN];
deque<int> q;
inline
bool check(ll x) {
for (int i = 1; i <= n + 1; i++) dp[i] = 0;
q.clear(), q.push_back(0);
for (int i = 1, j = 0; i <= n + 1; i++) {
for (; !q.empty() && s[i - 1] - s[q.front()] > x; q.pop_front());
dp[i] = a[i] + dp[q.front()];
for (; !q.empty() && dp[q.back()] >= dp[i]; q.pop_back());
q.push_back(i);
}
return dp[n + 1] <= x;
}
ll l, r, mid;
int main() {
for (scanf("%d", &T); T--;) {
scanf("%d", &n), a[n + 1] = 0;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
for (l = 1, r = s[n]; l < r; check(mid = l + r >> 1) ? r = mid : l = mid + 1);
printf("%lld\n", l);
}
}
```