admin管理员组文章数量:1602097
也许更好的阅读体验
D
e
s
c
r
i
p
t
i
o
n
\mathcal{Description}
Description
n
n
n个点,每个点有点权,有
m
m
m个区间,要选择一些点使得所有区间里都有点,求最小总点权
n
,
m
≤
5
×
1
0
5
n,m\le 5×10^5
n,m≤5×105
S
o
l
u
t
i
o
n
\mathcal{Solution}
Solution
广东省赛好水啊,感觉单挑都可以至少
6
6
6题
这题属于一眼题了,不知为何过的很少
设
f
i
f_i
fi表示
[
1
,
i
]
[1, i]
[1,i]这个区间全部满足条件并且选择了
i
i
i的最少花费
令
n
+
1
n+1
n+1有一个点且点权为
0
0
0,则答案就是
f
n
+
1
f_{n+1}
fn+1
转移方程
f
i
=
m
i
n
{
f
j
}
f_i=min\{f_j\}
fi=min{fj}其中要满足
[
j
+
1
,
i
−
1
]
[j+1,i-1]
[j+1,i−1]之间没有要求区间,考虑
j
j
j的合法区间,假设为
[
k
,
i
−
1
]
[k,i-1]
[k,i−1],当
i
i
i变为
i
+
1
i+1
i+1时,如果有一个区间以i结尾并且左端点在
[
k
,
i
]
[k,i]
[k,i]之间,那么对于
i
+
1
i+1
i+1来说,
j
j
j的区间会变小,这个过程中,
j
j
j的区间只会越来越往右变小,因此可以用单调栈维护这个
d
p
dp
dp
C
o
d
e
\mathcal{Code}
Code
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn = 5e5 + 10;
struct IO {
template <class T>
IO operator>>(T &res) {
res = 0;
char ch;
bool flag = false;
while ((ch = getchar()) > '9' || ch < '0') flag |= ch == '-';
while (ch >= '0' && ch <= '9') res = (res << 3) + (res << 1) + (ch ^ '0'), ch = getchar();
if (flag) res = ~res + 1;
return *this;
}
} cin;
int T, n, m, hd, ed;
int a[maxn], l[maxn], q[maxn];
ll f[maxn];
void solve ()
{
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], l[i] = 0;
cin >> m;
for (int i = 1, lt, rt; i <= m; ++i) {
cin >> lt >> rt;
l[rt] = max(l[rt], lt);
}
q[hd = ed = 1] = 0;
a[++n] = 0;
for (int i = 1; i <= n; ++i) {
f[i] = f[q[hd]] + a[i];
while (hd <= ed && f[q[ed]] > f[i]) --ed;
q[++ed] = i;
while (q[hd] < l[i]) ++hd;
}
printf("%lld\n", f[n]);
}
int main ()
{
cin >> T;
while (T--) solve();
return 0;
}
如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
本文标签: 广东省baseconstructionStation
版权声明:本文标题:2023广东省赛B Base Station Construction 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728397037a1157131.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论