昨晚 CF C 题解

cjdstttttt

2025-12-28 13:09:47

发布于：广东

18阅读

0回复

0点赞

要是正开的话，结果会不一样吗？

做题顺序：C->A->C->B。

题意解析：给定一个初始长度为 $n$ 的数组 $A$ 。你需要对 $A$ 进行 $n-1$ 次操作。每次操作如下：

你可以选择 $A_1$ 或 $A_2$ 。
如果你选择 $A_1$ ，将得分增加 $A_1$ ，并删除 $A_1$ 。
如果你选择 $A_2$ ，将得分增加 $-A_2$ ，并删除 $A_2$ 。
将剩余元素重新编号。

求最大得分。

$n\le 2\times 10^5,1\le\red{-10^9}\le A_i\le 10^9$ 。

思考半小时贪心无果，于是先打个 DP 再说。

注意到最终会剩一个元素，而那个元素是最终的 $A_1$ 。

所以我们可以记 $\text{dp}[i][j]$ 为前 $i-1$ 操作后 $A_1$ 是原来的 $A_j$ ，于是就有了很显然的 DP：

$\text{dp}[i][j]= \begin{cases} \max_{k=1}^{i-1}(\text{dp}[i-1][k]+A_k) & j=i\\ \text{dp}[i-1][j]-A_i & j<i\\ \end{cases}$

注意到这个很可以优化的样子！

首先滚动数组一下，记第 $i-1$ 次操作前的 DP 数组为 $\text{dp}$ ，操作后的 DP 数组为 $\text{dp}'$ ，则有如下：

$\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} (\text{dp}[k]+A_k) & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases}$

显然我们需要一个方法可以快速求出 $\max \text{dp}[k]+A_k$ ，还要将它整体减 $A_j$ 。

考虑一个新的 DP， $\text{dp}[j]$ 为原来的 $\text{dp}[j]+A_j$ ，这样就转化成了：

$\text{dp}'[j]= \begin{cases} \max_{k=1}^{i-1} \text{dp}[k] & j=i\\ \text{dp}'[j]=\text{dp}[j]-A_j\space\space & j\lt i \end{cases}$

最终答案：

$\text{ans}=\max_{i=1}^n \text{dp}[i]-A_i$

注意这样最开始的 $\text{dp}[1]$ 应该为 $A_1$ 而不是 $0$ 。

好了，顺眼多了。那就可以用线段树维护了。

namespace cjdst{
	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = std::max(tr[u << 1], tr[u << 1 | 1]);
		}
		void push_down(int u){
			tr[u << 1] += lazytag[u];
			tr[u << 1 | 1] += lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r){
			left[u] = l, right[u] = r;
			if(l == r){
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid);
			build(u << 1 | 1, mid + 1, r);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = -0x3f3f3f3f3f3f3fll;
			if(right[u << 1] >= l) ans = std::max(ans, _query(u << 1, l, r));
			if(left[u << 1 | 1] <= r) ans = std::max(ans, _query(u << 1 | 1, l, r));
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n){
			tr.resize(n * 4 + 5, -0x3f3f3f3f3f3f3fll);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};

	void solve(){
		int n;
		std::cin >> n;
		std::vector <ll> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
		}
		Segtree <ll> tr(n + 5);
		tr.modify(1, 1, 0x3f3f3f3f3f3f3fll + a[1]);
		for(int i = 2; i <= n; i++){
			tr.modify(i, i, 0x3f3f3f3f3f3f3fll + tr.query(1, i - 1) + a[i]);
			tr.modify(1, i - 1, -a[i]);
		}
		ll ans = -0x3f3f3f3f3f3f3fll;
		for(int i = 1; i <= n; i++){
			ans = std::max(ans, tr.query(i, i) - a[i]);
		}
		std::cout << ans << '\n';
	}
}