蒟蒻 Register_int 的小窝

蒟蒻 Register_int 的小窝

来啦,客官!

CF1918D 题解

posted on 2024-01-31 00:46:31 | under solution |

答案由两部分组成,一部分为加和,另一部分为 $\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 代码

#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);
    }
}