数组A包含N个元素A1, A2……AN。数组B包含N个元素B1, B2……BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= Bi。数组A的代价定义如下：
（公式表示所有两个相邻元素的差的绝对值之和）
给出数组B，计算可能的最大代价S。
Input
第1行：1个数N，表示数组的长度(1 <= N <= 50000)。
第2 - N+1行：每行1个数，对应数组元素Bi(1 <= Bi <= 10000)。
Output
输出最大代价S。
Input示例
5
10
1
10
1
10
Output示例
36
明确
分析： 题意很明确，每一项只和前 一项有关系， 很容易写出来一个超级暴力的解法
代码
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int N = (int) 50000 + 11;
const int M = (int) 10000 + 11;
const int MOD = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;// dp[i][j]表示 当第i个数为j的时候可以获得的最大代价，因为只和前一项有关系，所以可以用滚动数组来优化空间复杂度
int B[N];
int dp[2][N];
int main(){int n; scanf("%d",&n);int upp = 0;for(int i = 1; i <= n; i++)scanf("%d" ,&B[i]), upp = max(upp, B[i]);int cur = 1;for(int i = 2; i <= n; i++){memset(dp[cur ^ 1], 0, sizeof(int) * (upp + 2));for(int j = 1; j <= B[i]; j++){for(int k = 1; k <= B[i - 1]; k++){dp[cur ^ 1][j] = max(dp[cur ^ 1][j], dp[cur][k] + abs(j - k)); }}cur ^= 1;}int ans = 0;for(int i = 1; i <= B[n]; i++) ans = max(ans, dp[cur][i]);printf("%d\n", ans);return 0;
}
感觉应该就是这样DP，但是这个时间复杂度，我却怎么都降低不了，因为我感觉那个取最优过程 不是单调的，这怎么优化。
搜了题解，发现 每一步只需要取 最顶部和最底部就够了。这样的话，中间二重循环枚举就可以直接跳过，直接O（n）就可以搞定了。
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef unsigned long long ull;const int N = (int) 50000 + 11;
const int M = (int) 10000 + 11;
const int MOD = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;ll B[N];
ll dp[2][N];
int main(){int n; scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%lld" ,&B[i]);int cur = 1;for(int i = 2; i <= n; i++){dp[cur ^ 1][1] = dp[cur ^ 1][B[i]] = 0;dp[cur ^ 1][1] = max(dp[cur][B[i - 1]] + abs(1 - B[i - 1]), dp[cur][1]);dp[cur ^ 1][B[i]] = max(dp[cur][B[i - 1]] + abs(B[i] - B[i - 1]), dp[cur][1] + abs(B[i] - 1));cur ^= 1;}printf("%lld\n", max(dp[cur][B[n]], dp[cur][1]));return 0;
}