CF 1425 - E. Excitation of Atoms

题目链接

---

题意：

给 $n$ 个原子。每个原子有两种状态，静态和激发态。每个原子 $i$ 从静态转换到激发态需要消耗 $d[i]$ 的能量，而在激发态会贡献的 $a[i]$ 的能量。初始的时候，序号从 $1-n$ 的原子是按照编号顺序连接在一起的，也就是原子 $i$ 连接到原子 $i+1$。在激发原子时有一个连锁反应，就是被激发的原子会自动激发它连接的下一个原子，这个时候是不会消耗能量的。但是最后一个原子不能连接到任何一个原子。

给定 $K$，我们必须要改变 $K$ 个连接关系。有一个限定是不能连接到自己，也不能连接到原来连接的原子。比如初始时，原子 $a$ 连接到原子 $b$，那么我们改变这个连接关系时，原子 $a$ 不能连接到原子 $a$，也不能再次连接原子 $b$。

我们可以选择激发任意多个原子，问最终能得到最大的能量是多少。

---

思路：

1）当 $K>=2$ 时 ①我们总是能将所有原子全部激发。我们可以选择激发前 $N-1$ 个原子中（因为最后一个原子不能连接到任何的原子，所以不能作为激发原子）能量消耗 $d[i]$ 最小的那个原子 $i$ 以激发所有的原子。这样我们的收益就是：所有原子的能量和 - 原子 $i$ 能量消耗。

②我们还可以选择不改变原子的连接关系（虽然我们必须改变K次，但是我们可以改变了再改变回去哈哈哈），然后遍历激发每一个原子 $i$, 取（后缀能量和 - 当前原子消耗）的最大收益 $max(suffix[i]-d[i])$

2）当 $K==0$ 时 就只能不改变原来原子的连接关系，然后取 $max(suffix[i]-d[i])$

3）当 $K==1$ 时

第一种情况：

我们枚举断点 $i$, 断掉从点 $i$ 发出的边，然后将点 $i$ 连接到第一个点上（从2开始枚举，因为原子1不能连接到原子1）。然后这个原子就变成了两个部分： ① $[1,i]$ 的环； ② $[i+1,N]$ 的链。

对于第一个部分，就和 $K>=2$ 时的第一种情况类似，区间能量和-最小能量消耗即可。 对于第二个部分，就和 $K>=2$ 时的第二种情况类似，直接找到 $max(suffix[i]-d[i])$ 即可。 最后的结果自然就是两个部分相加了。

第二种情况： 我们枚举断点 $i$, 断掉从点 $i-1$ 连接到 $i$ 的边，并且连接到 $i+1$ 上。这样我们就成了一个如下图所示的样子。 这样的话我们考虑激发点在断点 $i$ 前 $[1,i-1]$，还是在其后 $[i,N]$。

如果在断点后，那就很简单就是像 $K>=2$ 时的第二种情况，直接找到 $max(suffix[i]-d[i])$ 即可。

如果在断点前，我们就需要找到 $[1,i-1]$ 这个区间内的 $max(suffix[i]-d[i])$ ，然后减去 $a[i]$。所以我们可以用线段树维护区间的 $max(suffix[i]-d[i])$ 。这个时候需要考虑单独的结点 $i$ 是不是有贡献，如果有正的贡献就加上。

最后的结果自然是激发点取断点前和断点后的最大值。

【关于为什么只间隔一个点呢，对于在断点后激发无影响。但是对于在断点前激发，那么断点后的能量和是确定的，我们对比的实际上是断点前那一段的 $max(suffix[i]-d[i])$ 。所以去掉更多的点，显然不是更优的策略。】

tips!!!

对于每种情况都必须考虑不激发的情况，也就是每种情况的结果都要和 $0$ 对比取最大值。

---

Code:

#include <bits/stdc++.h> #define MID (l + r) >> 1 #define lsn rt << 1 #define rsn rt << 1 | 1 #define Lson lsn, l, mid #define Rson rsn, mid + 1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define INF 0x3f3f3f3f using namespace std; typedef long long ll ; ll read() { ll res = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') f = -f; ch = getchar(); } while(ch >= '0' && ch <= '9') { res = res * 10 + ch - '0'; ch = getchar(); } return res * f; } const int maxN = 100005; int N, K; int a[maxN], d[maxN]; ll prefix[maxN]; ll _min[maxN]; ll dp[maxN]; //后缀 ll tree[maxN << 2]; void pushup(int rt) { tree[rt] = max(tree[lsn], tree[rsn]); } void build_tree(int rt, int l, int r) { if(l == r) { tree[rt] = prefix[N] - prefix[l - 1] - d[l]; return ; } int mid = MID; build_tree(Lson); build_tree(Rson); pushup(rt); } ll query(int rt, int l, int r, int ql, int qr) { if(ql <= l && qr >= r) { return tree[rt]; } int mid = MID; if(qr <= mid) return query(QL); if(ql > mid) return query(QR); return max(query(QL), query(QR)); } int main () { N = read(), K = read(); for(int i = 1; i <= N; ++ i ) { //收益 a[i] = read(); prefix[i] = prefix[i - 1] + (ll)a[i]; } for(int i = 1; i <= N; ++ i ) { //消耗 d[i] = read(); } ll MIN = d[1], min_pos = 1; _min[1] = min_pos; for(int i = 2; i < N; ++ i) { if(d[i] < MIN) { MIN = d[i]; min_pos = i; } _min[i] = min_pos; } dp[N + 1] = -INF; for(int i = N; i >= 1; -- i ) { dp[i] = max(dp[i + 1], prefix[N] - prefix[i - 1] - (ll)d[i]); } build_tree(1, 1, N); ll ans = 0; if(K >= 2){ ans = max(ans, prefix[N] - d[_min[N - 1]]); ans = max(ans, dp[1]); } else if(K == 0) { ans = max(ans, dp[1]); } else { //连向第一个点 for(int i = 2; i < N; ++ i ) { ll fir = prefix[i] - d[_min[i]]; if(fir < 0) fir = 0; ll sec = dp[i + 1]; if(sec < 0) sec = 0; ans = max(ans, fir + sec); } //连向后面的点 for(int i = 2; i < N; ++ i ) { //枚举断点i，跳过i点 割掉i - 1到i的边, ll left = max(query(1, 1, N, 1, i - 1) - (ll)a[i] + max(0ll, ll(a[i] - d[i])), 0ll); //从断点前激发 ll right = max(0ll, dp[i]); //从断点后激发 ans = max(left, ans); ans = max(right, ans); } } cout << ans << endl; return 0; } /* 4 1 2 5 2 1 101 2 101 100 ans: 7 4 0 5 3 2 2 13 8 5 1 ans: 1 4 1 10 10 9 100 1 10 10 1000000 ans: 119 */