2023广东省赛B Base Station Construction

也许更好的阅读体验

\(\mathcal{Description}\)
\(n\)个点，每个点有点权，有\(m\)个区间，要选择一些点使得所有区间里都有点，求最小总点权
\(n,m\le 5×10^5\)

\(\mathcal{Solution}\)
广东省赛好水啊，感觉单挑都可以至少\(6\)题
这题属于一眼题了，不知为何过的很少
设\(f_i\)表示\([1, i]\)这个区间全部满足条件并且选择了\(i\)的最少花费
令\(n+1\)有一个点且点权为\(0\)，则答案就是\(f_{n+1}\)
转移方程\(f_i=min\{f_j\}\)其中要满足\([j+1,i-1]\)之间没有要求区间，考虑\(j\)的合法区间，假设为\([k,i-1]\)，当\(i\)变为\(i+1\)时，如果有一个区间以i结尾并且左端点在\([k,i]\)之间，那么对于\(i+1\)来说，\(j\)的区间会变小，这个过程中，\(j\)的区间只会越来越往右变小，因此可以用单调栈维护这个\(dp\)
\(\mathcal{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;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧