【标题来源】
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[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 2
- out:
- 0 2 0 5 2 10 10
- */
【参考文献】
https://www.acwing.com/solution/content/201365/
https://www.acwing.com/solution/content/196866/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
