Codeforces Round 922 (Div. 2) D题 Blocking Elements（单调队列优化dp）

题目链接

https://codeforces.com/problemset/problem/1918/D

思路

我们很容易想到二分答案。

假设我们已经确定答案不会超过$x$，那么有：两个屏蔽点间的元素和不大于$x$，所有屏蔽点的权值和不大于$x$。

我们在原序列的基础上加上两个虚拟点$a_0=a_{n+1}=0$，我们设$d{p}_i$表示考虑前$i$个位置，且两个屏蔽点间的元素和的最大值不超过$x$的最小代价，状态转移方程为：

$dp[i]=a[i]+min(dp[j])$，其中$j<i$ 并且$s[i-1]-s[j]\le x$，$s$为$a$的前缀和数组。

因为每次转移到$i$的区间，无论是前缀和数组$s$还是$dp$数组都单调递增，因此我们可以使用单调队列优化$dp$，将时间复杂度降至线性。

最后$dp[n+1]$即为最终答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n;
int a[N], s[N], dp[N];
deque<int>q;
bool check(int x)
{q.clear();for (int i = 1; i <= n + 1; i++)dp[i] = 0;q.push_back(0);for (int i = 1; i <= n + 1; i++){while (q.size() && s[i - 1] - s[q.front()] > x) q.pop_front();dp[i] = a[i] + dp[q.front()];while (q.size() && dp[q.back()] >= dp[i]) q.pop_back();q.push_back(i);}return dp[n + 1] <= x;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}a[n + 1] = 0;for (int i = 1; i <= n + 1; i++)s[i] = s[i - 1] + a[i];int low = 0, high = 1e14;while (low < high){int mid = low + high >> 1;if (check(mid)){high = mid;}else low = mid + 1;}cout << high << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}