自动搬运

查看原文

来自洛谷，原作者为

	kyel **

搬运于2025-08-24 21:35:35，当前版本为作者最后更新于2019-04-14 00:27:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

标签：线段树，单调队列，动态规划。

令front[i]表示最近的不能和i共区间的元素位置，显然front[i]可以在输入时通过取最大值处理出来。显然，i不能和front[i]以及位置更靠前的元素划为一段。

令dp[i]表示使区间[1, i]中的元素合法分段所需要的最小代价

考虑向位置i转移，假设有位置j在i前且合法。则要么dp[i] = dp[i - 1] + k，即元素i单独分一段，要么找到某个值j使得dp[j] + cost(j + 1, i)最小。其中cost(j + 1, i) = s * (Max(j + 1, i) - Min(j + 1, i)),即将区间[j + 1, i]分为一段的代价。

显然，重点在于如何高效地找到j使得dp[j] + cost(j + 1, i)最小。

用线段树维护。线段树维护的是从之前某一位置j进行转移且将位置j与当前位置划为一段的最小代价，当然使用时是区间查询而不关心具体位置。假定我们已经求得了dp[i]，且将区间[j, i - 1]划为一段的代价记为V0，那么我们发现，如果有位置j < i且Vj为Min(j + 1, i - 1)且Vi < Vj，即在位置j之后除了Vi没有比Vj小的值，那么如果位置i+1希望从j位置或者更靠前一些的位置转移，则代价为V0 + s * (Vj - Vi)，因为Vi取代了Vj最小值的地位，需要补上增加的代价。为什么说是更靠前“一些”呢？因为位置j之前可能有比Vj还小的元素，而这个时候如果有Vk > Vi，那么对应需要增加的代价就是s * (Vk - Vi)。因此，这些位置是从后往前值递减的，因为如果出现了位置j > k且Vj < Vk，那么k不可能是之后计算代价用到的最小值，我们就不再关心了。因此，可以用一个从前往后单调递增的单调队列Min来维护这个位置的序列，然后用线段树做区间加法维护最小代价。

最大值同理利用单调队列维护。

显然，文字叙述过于繁琐，更简明的思路请参照代码。

#include <cstdio>
#include <cstdlib>

#include <deque>
#include <algorithm>

namespace my {
	template <class T> inline void getmax(T& a, T b) { if (b > a) a = b; }
	template <class T> inline void getmin(T& a, T b) { if (b < a) a = b; }
}
const int maxn(112345);
namespace seg {
	long long val[maxn << 2], tag[maxn << 2];
#define ls (n << 1)
#define rs (n << 1 | 1)
	inline void push(int n) {
		if (tag[n]) {
			val[ls] += tag[n], tag[ls] += tag[n];
			val[rs] += tag[n], tag[rs] += tag[n];
			tag[n] = 0;
		}
	}
	inline void update(int n) {
		val[n] = std::min(val[ls], val[rs]);
	}
	long long quary(int n, int left, int right, int l, int r) {
		if (left == l && right == r) {
			return val[n];
		}
		push(n);
		int mid(left + right >> 1);
		if (r <= mid) return quary(ls, left, mid, l, r);
		else if (l > mid) return quary(rs, mid + 1, right, l, r);
		return std::min(quary(ls, left, mid, l, mid), quary(rs, mid + 1, right, mid + 1, r));
	}
	void modify(int n,int left, int right, int l, int r, long long v) {
		if (left == l && right == r) {
			val[n] += v, tag[n] += v;
			return;
		}
		push(n);
		int mid(left + right >> 1);
		if (r <= mid) modify(ls, left, mid, l, r, v);
		else if (l > mid) modify(rs, mid + 1, right, l, r, v);
		else modify(ls, left, mid, l, mid, v), modify(rs, mid + 1, right, mid + 1, r, v);
		update(n);
	}
}
std::deque<int> min, max;
int n, m, front[maxn];
long long k, s, v[maxn], dp[maxn];
void solve() {
	int f(0);
	for (int i(1); i <= n; ++i) {
		my::getmax(f, front[i]);
		while (!min.empty() && min.front() <= f) min.pop_front();
		int fp(i - 1);//在fp之后的最小值不是v[min.back()]，因此只加区间[fr + 1, fp]
		while (!min.empty() && v[min.back()] >= v[i]) {
			//v[i]取代v[pos]成为之后的最小值，v[pos]对之后无“贡献” 
			int pos(min.back()); min.pop_back();
			int fr(min.empty() ? f : min.back());
			seg::modify(1, 1, n, fr + 1, fp, s * (v[pos] - v[i]));
			//v[i]取代v[pos]成为之后的最小值，故增加s * (v[pos] - v[i])
			fp = fr;
		} min.push_back(i);
		while (!max.empty() && max.front() <= f) max.pop_front();
		fp = i - 1;
		while (!max.empty() && v[max.back()] <= v[i]) {
			int pos(max.back()); max.pop_back();
			int fr(max.empty() ? f : max.back());
			seg::modify(1, 1, n, fr + 1, fp, s * (v[i] - v[pos]));
			fp = fr;
		} max.push_back(i);
		dp[i] = dp[i - 1] + k;
		if (f + 1 < i) my::getmin(dp[i], seg::quary(1, 1, n, f + 1, i) + k);
		//从[f + 1, i]中找到一个最合适的位置p使得p与i划分为一段且总代价最小
		if (i != n)	seg::modify(1, 1, n, i + 1, i + 1, dp[i]);
		//读者可以体会一下为什么要在i + 1处加上dp[i]以及为什么这么做是对的 
	}
	printf("%lld\n", dp[n]);
}
int main() {
	scanf("%d%d%lld%lld", &n, &m, &k, &s);
	for (int i(1); i <= n; ++i) scanf("%d", v + i);
	for (int i(0); i != m; ++i) {
		int a, b; scanf("%d%d", &a, &b);
		if (a > b) std::swap(a, b);
		my::getmax(front[b], a);
	}
	solve();
	return 0;
}