AcWing 5166：对称山脉 ← 动态规划

【题目来源】
https://www.luogu.com.cn/problem/P9325
https://www.acwing.com/problem/content/5169/

【题目描述】
有 N 座山排成一排，从左到右依次编号为 1∼N。
其中，第 i 座山的高度为 hi。
对于一段连续的山脉，我们使用如下方法定义该段山脉的不对称值。
如果一段连续的山脉由第 l∼r（1≤l≤r≤N）座山组成，那么该段山脉的不对称值为 。

现在，你需要回答 N 个问题，问题编号 1∼N。
其中，第 i 个问题的内容是：请计算，一段恰好包含 i 座山的连续山脉（即长度为 i 的连续区间）的不对称值的最小可能值。

备注：山脉不对称值计算公式的 LaTex 代码如下所示。

\sum\limits_{i=0}\limits^{\frac{r-l}{2}} |h_{l+i}-h_{r-i}|

【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 h1, h2, …, hN。

【输出格式】
输出一行 N 个整数，其中第 i 个数表示第 i 个问题的答案。

【数据范围】
1≤N≤5000, 0≤hi≤10^5

【输入样例1】
7
3 1 4 1 5 9 2

【输出样例1】
0 2 0 5 2 10 10

【样例解释1】
关于第 5 个问题的答案为什么是 2，见如下解析。
让我们依次列举所有长度为 5 的连续区间并计算区间不对称值：
区间 [3,1,4,1,5] 的不对称值为 |3−5|+|1−1|+|4−4|=2。
区间 [1,4,1,5,9] 的不对称值为  |1−9|+|4−5|+|1−1|=9 。
区间 [4,1,5,9,2] 的不对称值为 |4−2|+|1−9|+|5−5|=10。
由上可知，不对称值的最小可能值为 2。

【输入样例2】
4
1 3 5 6

【输出样例2】
0 1 3 7

【样例解释2】
注意，长度为 4 的连续区间只有 [1,3,5,6]，其不对称值为  |1−6|+|3−5|=7。

【算法分析】
● 本题 N 最大 5000，最多 2500 对儿，每对儿的最大差值为 10^5，故山脉的不对称值最大为 2500×10^5=2.5×10^8，没有达到 10^9，所以不会爆 int。
● 状态 dp[i][j] 表示以第 i 个山开始的连续 j 个山组成的山脉的不对称值。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=5005;
int h[maxn];
int ans[maxn];
int dp[maxn][maxn];int main() {int n;cin>>n;for(int i=1; i<=n; i++) cin>>h[i];memset(ans,0x3f,sizeof ans);ans[1]=0;for(int k=1; k<n; k++) {for(int i=1; i<=n-k; i++) {dp[i][k+1]=dp[i+1][k-1]+abs(h[i]-h[i+k]);ans[k+1]=min(ans[k+1],dp[i][k+1]);}}for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
}/*
in:
7
3 1 4 1 5 9 2out:
0 2 0 5 2 10 10
*/

【参考文献】
https://www.acwing.com/solution/content/201365/
https://www.acwing.com/solution/content/196866/