专栏文章

P11743 Dynamic Array Problem题解

__InRedBrother_QWQ_
P11743题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@min5f0fh
此快照首次捕获于
2025/12/01 20:51
3 个月前
此快照最后确认于
2025/12/01 20:51
3 个月前
查看原文

写作原因

一是为社区做贡献，
二是此题很有趣。

题意

题目描述地很详细，就不用复数了。

正解

由于要求一个元素至多被翻转一次，所以本题先可看作从长度为 nn 的序列 AA 中找出 KK 个互不相交的连续字段，将其内部翻转后求最大总贡献。
由于数据范围 n∈[1,550]n \in [1, 550]，所以可以想到作为 DP 的状态，同时我们可以 O(n2)O(n ^ 2) 预处理出：
  • X0,l,rX_{0, l, r}：子段 [l,r][l, r] 保持原样的最大贡献值；
  • X1,l,rX_{1, l, r}：子段 [l,r][l, r] 内部翻转的最大贡献值；
当然，这个值可不能用文中那个公式直接计算，毕竟内部翻转的子段 [l,r][l, r] 中间插入某些隔板可能会让值更优，而且不影响除 [l,r][l, r] 外的其他子段（内部翻转不影响隔板位置，我们才能先翻转后考虑插入隔板）。
假设选择翻转或不翻转后的子段。
al,al+1,al+2,…,ar−2,ar−1,ara_l, a_{l + 1}, a_{l + 2},\ldots, a_{r - 2}, a_{r - 1}, a_r
对于这个子段的最大值计算，可以。
  • 从前往后；
  • 从后往前。

从前往后

按照公式，一步步计算。
不过无法考虑中间插板是否有最优。
有 dalao 可以这样考虑最优的话请指教。

从后往前

我们考虑。
  • 子段 [r,r][r, r]。 X0/1,r,r=ar;X_{0/1, r, r} = a_r;
  • 子段 [r−1,r][r - 1, r]。 X0/1,r−1,r=ar−1+2ar;X_{0/1, r - 1, r} = a_{r - 1} + 2 a_r;
  • 子段 [r−2,r][r - 2, r]。 X0/1,r−2,r=ar−2+2ar−1+3ar;X_{0/1, r - 2, r} = a_{r - 2} + 2 a_{r - 1} + 3 a_r;
  • ……
所以我们可以推出结论。
Xi,l,r=Xi,l+1,r+∑j=lrajX_{i, l, r} = X_{i, l + 1, r} + \sum_{j = l}^{r} a_j
后面的 ∑\sum 可以实时维护。
但如何保证子段的贡献最优呢？
我们可以先将答案更新，然后判断：如果 ∑\sum 的值是负数，就将其置为 00，相当于在这之间插入一块隔板。

证明

al,al+1,…,aI,aI+1,…,aJ,aJ+1,…,ar−1,ara_l, a_{l + 1}, \ldots, a_I, a_{I + 1}, \ldots, a_J, a_{J + 1}, \ldots, a_{r - 1}, a_{r}
设从 aIa_I 到 aJ−1a_{J - 1} 之间和为负数，aJa_{J} 及之后是上一次插板的地方，已经处理过的，那么不在这里插板子的贡献。
Xi,l,r=∑i=lI−1ai×(i−l+1)+∑i=IJ−1ai×(i−l+1)+…X_{i, l, r} = \sum_{i = l}^{I - 1} a_i \times (i - l + 1) + \sum_{i = I}^{J - 1} a_i \times (i - l + 1) + \ldots
在这里插板子的贡献。
Xi,l,r=∑i=lI−1ai×(i−l+1)+∑i=IJ−1ai×(i−I+1)+…X_{i, l, r} = \sum_{i = l}^{I - 1} a_i \times (i - l + 1) + \sum_{i = I}^{J - 1} a_i \times (i - I + 1) + \ldots
其中省略号表示已经处理过的部分。细节后半段，可以看出后者明显更优，因为后者比前者少了这么多：(I−l)×∑i=Irai(I - l) \times \sum_{i = I}^{r} a_i。
而又已知 ∑\sum 的部分值为负数，且插入隔板对还未处理过的部分没有影响，所以后者较前者更多。
有个疑问：边界值 aIa_I 是放在隔板前还是隔板后呢？
答：放在隔板之后。当和累加到 aIa_I 时突然变成负数，说明 aIa_I 是个大得不得了的负数，放在隔板之前的话，他在 Xi,l,rX_{i, l, r} 中的贡献为 aI×(I−l)a_I \times (I - l)，放在隔板之后则为 aI×1a_I \times 1，明显更大。所以放在隔板之后。
实现：
C
	for(int i = 1; i <= n; i ++) {
		X[0][i][i] = X[1][i][i] = A[i];

		sum = A[i];
		for(int j = i - 1; j >= 1; j --) {
			sum += A[j];
			X[0][j][i] = X[0][j + 1][i] + sum;
			if(sum < 0) sum = 0;
		}
		sum = A[i];
		for(int j = i + 1; j <= n; j ++) {
			sum += A[j];
			X[1][i][j] = X[1][i][j - 1] + sum;
			if(sum < 0) sum = 0;
		}
	}

预处理完所有子段

考虑 DP。我们设数组 dpi,jdp_{i, j} 表示在前 ii 个元素的序列中翻转 jj 次，所得的最大总贡献。
转移如下。
dpi,j=max⁡(max⁡k=0i−1dpk,j+X0,k+1,i,max⁡k=0i−1dpk,j−1+X1,k+1,i)dp_{i, j} = \max(\max_{k = 0}^{i - 1} dp_{k, j} + X_{0, k + 1, i}, \max_{k = 0}^{i - 1} dp_{k, j - 1} + X_{1, k + 1, i})
代码实现：
C
	for(int i = 0; i <= n; i ++)
		for(int k = 0; k <= K; k ++)
			dp[i][k] = -MX;
	dp[0][0] = 0;
	for(int i = 1; i <= n; i ++) {
		for(int k = 0; k <= min(K, i); k ++) {
			for(int j = 0; j < i; j ++) {
				if(-MX != dp[j][k]) dp[i][k] = max(dp[i][k], dp[j][k] + X[0][j + 1][i]);
				if(k >= 1 && -MX != dp[j][k - 1]) dp[i][k] = max(dp[i][k], dp[j][k - 1] + X[1][j + 1][i]);
			}
		}
	}

最终代码

C
#include <bits/stdc++.h>
#define int long long
using namespace std;

int t = 1;

const int N = 605, MX = 0x3f3f3f3f3f3f3f3f;
int n, A[N], sum;
int K, ans = -MX;

int X[2][N][N], dp[N][N];

void solve() {
	cin >> n >> K;
	for(int i = 1; i <= n; i ++) cin >> A[i];

	for(int i = 1; i <= n; i ++) {
		X[0][i][i] = X[1][i][i] = A[i];

		sum = A[i];
		for(int j = i - 1; j >= 1; j --) {
			sum += A[j];
			X[0][j][i] = X[0][j + 1][i] + sum;
			if(sum < 0) sum = 0;
		}
		sum = A[i];
		for(int j = i + 1; j <= n; j ++) {
			sum += A[j];
			X[1][i][j] = X[1][i][j - 1] + sum;
			if(sum < 0) sum = 0;
		}
	}

	for(int i = 0; i <= n; i ++)
		for(int k = 0; k <= K; k ++)
			dp[i][k] = -MX;
	dp[0][0] = 0;
	for(int i = 1; i <= n; i ++) {
		for(int k = 0; k <= min(K, i); k ++) {
			for(int j = 0; j < i; j ++) {
				if(-MX != dp[j][k]) dp[i][k] = max(dp[i][k], dp[j][k] + X[0][j + 1][i]);
				if(k >= 1 && -MX != dp[j][k - 1]) dp[i][k] = max(dp[i][k], dp[j][k - 1] + X[1][j + 1][i]);
			}
		}
	}

	for(int k = 0; k <= K; k ++) ans = max(ans, dp[n][k]);
	cout << ans;
}

signed main() {
//	freopen("ex_box4.in", "r", stdin);
//	freopen("box.in", "r", stdin);
//	freopen("box.out", "w", stdout);

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

//	cin >> t;
	while(t --) {
		solve();
	}
	return 0;
}
谢谢。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...