526互联

落基山脉（区间dp）

发布时间 2023-09-23 16:18:58作者: shunn

  • 题意

题目链接：https://www.luogu.com.cn/problem/P9325

给一段山脉的高度，然后从中截取一段长度为 i 的区间，求最小不对称值。不对称值就是这段区间里，最左边的高度与最右边的高度的差值加上倒数第二和第二，……。然后输出区间长度从 1 到 n 的最小不对称值。

  • 思路

很容易想到暴力写法，n^3。显然不行。
区间dp，先枚举区间长度，然后枚举左端点。这里的区间dp不太一样，是枚举的中点。因为这是对称的，所以我们还需要看是奇是偶。如果是奇数，那么 dp[i] = dp[i-2] 加上新添加的左右端点差值。偶数同理，只是下标不一样。

dp[i][j] 代表长度为 i ，中点下标为 j 时最小的不对称值。

  • 代码

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<math.h>
#include<stack>
#include<map>
#include<list>
#include<unordered_set>
#include<unordered_map>
#define endl '\n';
//#define int long long;
using namespace std;
typedef long long ll; 
const int N = 5e3+10;
int n, m, k;
ll a[N], dp[N][N], h[N];

void sovle(){
    cin >> n;
    for (int i = 1; i <= n; i ++)cin >> a[i], h[i] = 3e9;

    for (int i = 2; i <= n; i ++){
        for (int j = 1; j <= n; j ++){
            int k = i / 2;
            int flag = 0;
            if (i%2)flag = 1;
            if (flag && (j - k < 1 || j + k > n))continue;
            else if (!flag && (j - k + 1 < 1 || j + k > n))continue;
            else {
                if (flag)dp[i][j] = dp[i-2][j] + abs(a[j-k] - a[j+k]);
                else dp[i][j] = dp[i-2][j] + abs(a[j-k+1] - a[j+k]);
                h[i] = min(h[i], dp[i][j]);
            }
        }
    }

    cout << "0";
    for (int i = 2; i <= n; i ++){
        cout << " " << h[i];
    }
}

int main()
{	
    int t = 1; 
    //scanf("%d", &t);
    
    while (t --){
        sovle();
    }

    return 0;
}