LuoguP6563 [SBCOI2020] 一直在你身旁

Description

给定长度为 nn (1n7.1×103)\left(1\leq n\leq7.1\times10^3\right) 的序列 aa (1ai109)\left(1\leq a_i\leq10^9\right) .
有一未知整数 x[1,n]x\in\left[1,n\right] ,判断 xx 是否大于 ii 的代价为 aia_i .
现保证序列 aa 单调不降,求能确保求出 xx 所需的最小代价。
TT (1T5×102)\left(1\leq T\leq5\times10^2\right) 组测试,保证 n7.1×103\sum n\leq7.1\times10^3 .


Solution

考虑 DP ,记 dpi,jdp_{i,j} 为确定 x[i,j]x\in\left[i,j\right] 后能确保求出 xx 所需的最小代价。
x[i,j]x\in\left[i,j\right] 说明 xajx\leq a_j ,则有状态转移方程

dpi,j=minik<j{max(dpi,k,dpk+1,j)+ak}dp_{i,j}=\min_{i\leq k<j}\left\{\max\left(dp_{i,k},dp_{k+1,j}\right)+a_k\right\}

边界条件 dpi,i=0dp_{i,i}=0 .

直接 DP 的时间复杂度为 O(n3)\mathcal O\left(n^3\right) ,考虑优化。
显然要考虑去掉状态转移方程中的 max\max .
注意到 dpi,kdp_{i,k} 关于 kk 单调不降dpk+1,jdp_{k+1,j} 关于 kk 单调不升

fi,j=min{kk[i,j), dpi,kdpk+1,j}f_{i,j}=\min\left\{k\big|k\in\left[i,j\right),\ dp_{i,k}\geq dp_{k+1,j}\right\}

i<ji<j 时,dpi,j1dpj,j=0dp_{i,j-1}\geq dp_{j,j}=0 ,故 fi,jf_{i,j} 必定存在。
kkfi,jf_{i,j} 的大小关系 分类讨论 即可,则
k<fi,jk<f_{i,j} 时,只需求最小的 dpk+1,j+akdp_{k+1,j}+a_k ,用 单调队列 维护即可。
kfi,jk\geq f_{i,j} 时,只需求最小的 dpi,k+akdp_{i,k}+a_k .
显然 dpi,k+akdp_{i,k}+a_k 关于 kk 单调不降,取 k=fi,jk=f_{i,j} 即可。
为了方便单调队列的维护,DP 时应先枚举 jj 再倒过来枚举 ii .

最后考虑如何求 fi,jf_{i,j} .
枚举 i,ji,j 后显然可以 二分fi,jf_{i,j} .
但这样总时间复杂度为 O(n2logn)\mathcal O\left(n^2\log n\right) ,不稳。
注意到 fi,j+1fi,j, fi1,jfi,jf_{i,j+1}\geq f_{i,j},\ f_{i-1,j}\leq f_{i,j} ,满足 决策单调性
于是就把时间复杂度中的 logn\log n 给优化掉了。

时间复杂度:O(n2)\mathcal O\left(n^2\right) .


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct node {
int p;
ll v;
node(int a = 0, ll b = 0): p(a), v(b) {}
};

const int N = 7.1e3 + 5;
const ll inf = 1e18 + 5;
int t, n, a[N];
ll dp[N][N];
deque<node> q;

void solve(void);

int main(void) {
scanf("%d", &t);
while (t--) solve();
return 0;
}

void solve(void) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
for (int j = 2; j <= n; j++) {
while (!q.empty()) q.pop_front();
for (int i = j - 1, k = i; i; i--) {
while (k > i && dp[i][k - 1] >= dp[k][j]) k--;
ll v = dp[i + 1][j] + a[i];
while (!q.empty() && q.back().v >= v) q.pop_back();
q.emplace_back(i, v);
while (!q.empty() && q.front().p >= k) q.pop_front();
dp[i][j] = min(q.empty() ? inf : q.front().v, dp[i][k] + a[k]);
}
}
printf("%lld\n", dp[1][n]);
}

Tsukkomi

题目背景是 CLANNAD ~ 好评!

Welcome to my other publishing channels