题解：P9325 [CCC 2023 S2] Symmetric Mountains

xhxxwcr · 2024-07-06 15:39:50 · 题解

一道区间 dp。
首先，我们需要知道，以 i 为头，以 j 为尾的长度为 l 的子串，他的值是多少，很容易可以得到：

其中，dp_{i,j} 表示以 i 为头，以 j 为尾的子串的值。他的值就等于把头尾去掉后剩下子串的值加上头尾的差值。
所以，我们需要求出长度为 l 的子串差值的最小值，只需要遍历头，遍历长度即可。

正解代码

#include<bits/stdc++.h>
using namespace std;
int dp[5010][5010],a[5010],n;
int main(){
  /*输入*/
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
  /*dp*/
    for(int l = 0;l < n;l++){//枚举长度
        int ans = 2e9;//初始化此处答案
        for(int i = 1;i + l <= n;i++){//枚举头
            int j = i + l;//计算尾
            dp[i][j] = dp[i + 1][j - 1] + abs(a[i] - a[j]);//dp
            ans = min(dp[i][j],ans);//计算最小值
        }
        cout << ans << " ";//输出最小值
    }
    return 0;
}