自动搬运

查看原文

来自洛谷，原作者为

	LFL **

搬运于2025-08-24 23:09:54，当前版本为作者最后更新于2025-02-14 19:11:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

出题人题解。

前置

易得：

• 翻转时隔板固定和不固定对最终的最大值没影响，所以隔板可以当成不固定来看。

• 由上文可以得到：求翻转后大区间最大的权值，其实就是求把大区间划分为多个小区间，翻转每个小区间后的权值的和的最大值

  例：原区间：| 1 | 2 3 | 4 5|， 翻转整个区间，则变为：| 5 4 | 3 2 | 1 |，此时的权值与 | 1 | 3 2 | 5 4 | 相同。

注：此部分在正解预处理或暴力贪心时会有用。

Subtask 1 (15 pts)：$n\leq20$。

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

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

可以改变一下顺序，先选 $k$ 个互不重叠的区间进行翻转，然后在每个区间的两端插入隔板。这样，问题退化为分割问题。

考虑 dp：$dp_{i,j}$ 表示考虑前 $i$ 个元素，翻转 $j$ 次的最大权值，则转移为：

$$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)$ 表示翻转 $[i,j]$ 后，在这一段区间插入隔板可以做到此区间的最大权值。

$cost(i,j)$ 表示不翻转 $[i,j]$ 后，在这一段区间插入隔板可以做到此区间的最大权值。

dp 预处理 $cost$ 和 $calc$ 即可做到 $O(n^3)$。

#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;
}