题解：P11743 Dynamic Array Problem
_Sparktasia_
·
·
题解
出题人题解。
前置
易得：
-
翻转时隔板固定和不固定对最终的最大值没影响，所以隔板可以当成不固定来看。
-
由上文可以得到：求翻转后大区间最大的权值，其实就是求把大区间划分为多个小区间，翻转每个小区间后的权值的和的最大值
例：原区间：| 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)\}\}
$cost(i,j)$ 表示不翻转 $[i,j]$ 后，在这一段区间插入隔板可以做到此区间的最大权值。
dp 预处理 $cost$ 和 $calc$ 即可做到 $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;
}
```