专栏文章

题解：P11743 Dynamic Array Problem

__Sparktasia_
P11743题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miq998vy
此快照首次捕获于
2025/12/04 01:02
3 个月前
此快照最后确认于
2025/12/04 01:02
3 个月前
查看原文
出题人题解。

前置

易得：
  • 翻转时隔板固定和不固定对最终的最大值没影响，所以隔板可以当成不固定来看。
  • 由上文可以得到：求翻转后大区间最大的权值，其实就是求把大区间划分为多个小区间，翻转每个小区间后的权值的和的最大值
    例：原区间：| 1 | 2 3 | 4 5|， 翻转整个区间，则变为：| 5 4 | 3 2 | 1 |，此时的权值与 | 1 | 3 2 | 5 4 | 相同。
注：此部分在正解预处理或暴力贪心时会有用。

Subtask 1 (15 pts)：n≤20n\leq20。

暴力枚举隔板，然后贪心。

Subtask 2~3 (100 pts)：n≤550n\leq550。

可以改变一下顺序，先选 kk 个互不重叠的区间进行翻转，然后在每个区间的两端插入隔板。这样，问题退化为分割问题。
考虑 dp：dpi,jdp_{i,j} 表示考虑前 ii 个元素，翻转 jj 次的最大权值，则转移为：
dpij=max⁡{max⁡k=ji{dpk−1,j−1+calc(k,i)},max⁡k=j+1i{dpk−1,j+cost(k,i)}}dp_{ij}=\max\{\max\limits_{k=j}^{i} \{dp_{k-1,j-1} + calc(k,i)\},\max\limits_{k=j + 1}^{i} \{dp_{k-1,j} + cost(k,i)\}\}
calc(i,j)calc(i,j) 表示翻转 [i,j][i,j] 后，在这一段区间插入隔板可以做到此区间的最大权值。
cost(i,j)cost(i,j) 表示不翻转 [i,j][i,j] 后，在这一段区间插入隔板可以做到此区间的最大权值。
dp 预处理 costcost 和 calccalc 即可做到 O(n3)O(n^3)。
CPP
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;

const int MAXN = 555;
int n, K, a[MAXN], dp[MAXN][MAXN], sum[2][MAXN][MAXN], val[2][MAXN][MAXN];

signed main(){
	IOS;
	cin >> n >> K;
	for(int i = 1; i <= n; i++) cin >> a[i];
	//预处理 
	
	memset(sum, 0xc0, sizeof sum);
	memset(dp, 0xc0, sizeof dp);
	//每个区间不翻转且中间没有隔板时的权值 
	for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++)
			val[0][i][j] = val[0][i][j - 1] + a[j] * (j - i + 1);
	//每个区间翻转且中间没有隔板时的权值 
	for(int i = 1; i <= n; i++)
		for(int j = i; j >= 1; j--)
			val[1][j][i] = val[1][j + 1][i] + a[j] * (i - j + 1);
	//每个区间不翻转且中间可以有隔板时的最大权值 
	for(int i = 1; i <= n; i++)
		for(int j = i; j <= n; j++){
			sum[0][i][i - 1] = 0;
			for(int k = j; k >= i; k--)
				sum[0][i][j] = max(sum[0][i][j], sum[0][i][k - 1] + val[0][k][j]); 
		}
	//每个区间翻转且中间可以有隔板时的最大权值 
	for(int i = 1; i <= n; i++)
		for(int j = i; j >= 1; j--){
			sum[1][i + 1][i] = 0;
			for(int k = j; k <= i; k++)
				sum[1][j][i] = max(sum[1][j][i], sum[1][k + 1][i] + val[1][j][k]);//由前置可得，求翻转后大区间最大的权值，其实就是求把大区间划分为多个小区间，翻转每个小区间后的权值的和的最大值 
		}

	//初始化 
	dp[0][0] = 0;
	for(int i = 1; i <= n; i++) dp[i][0] = sum[0][1][i];
	
	//DP 
	int ans = dp[n][0];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= min(i, K); j++){
			for(int k = i; k >= j; k--){
				dp[i][j] = max(max(dp[i][j], dp[k - 1][j] + sum[0][k][i]), dp[k - 1][j - 1] + sum[1][k][i]);
			}
			if(i == n) ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
	return 0;
}

评论

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

正在加载评论...