题意：
给你一个长度为n的序列。对于每一个k,k∈[1,n].问你将其分成k个段,每个段的贡献为该段最大值-最小值。贡献总和最大值是多少.n≤1e3
分析：
很好写出一个朴素的dp
dp[i][k]=dp[j][k-1]+MAX a(j+1,i)-MIN a(j+1,i) 其中0<j<i
但是复杂度不允许 此时想如果能优化就好了 但是最大最小压根没法优化 没有传递性 所以此时再想优化一定会暴毙的
但是dp[i][k]一定是跑不掉的 这两维一定是固定的
考虑每个数是否造成贡献 一个数可能对贡献+ 对贡献— 不选他贡献0 选两次他贡献0 这四种情况
所以重新设计状态 dp[i][j][0/1/2] 表示 前i个数分成了j段 第i个数 0不造成贡献 1对贡献- 2对贡献+
最大化所选的数之和 最优解一定是每段的最大-最小
非常巧妙 用另一种描述的最优解 同样是题意的正解
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
int a[maxn] , dp[maxn][maxn][3];
int main()
{
for (int i = 0 ; i < maxn ; i++)
for (int j = 0 ; j < maxn ; j++)
for (int k = 0 ; k <= 2 ; k++)
dp[i][j][k] = -inf;
ios::sync_with_stdio(false);
int n; cin >> n;
for (int i = 1 ; i <= n ; i++) cin >> a[i];
dp[1][0][0] = 0;
for (int i = 1 ; i <= n ; i++){
for (int j = 0 ; j < i ; j++){
if (dp[i][j][0] != -inf){
// 不填
dp[i + 1][j][0] = max(dp[i + 1][j][0] , dp[i][j][0]);
// 填一个-1
dp[i + 1][j][2] = max(dp[i + 1][j][2] , dp[i][j][0] - a[i]);
// 填一个1
dp[i + 1][j][1] = max(dp[i + 1][j][1] , dp[i][j][0] + a[i]);
// 同时填 +1 -1
dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0] , dp[i][j][0]);
}
if (dp[i][j][1] != -inf){
// 不填
dp[i + 1][j][1] = max(dp[i + 1][j][1] , dp[i][j][1]);
// 填一个-1
dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0] , dp[i][j][1] - a[i]);
}
if (dp[i][j][2] != -inf){
// 不填
dp[i + 1][j][2] = max(dp[i + 1][j][2] , dp[i][j][2]);
// 填一个+1
dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0] , dp[i][j][2] + a[i]);
}
}
}
for (int i = 1 ; i <= n ; i++){
cout << dp[n + 1][i][0] << endl;
}
return 0;
}