P9325 的题解捏

Loser_Syx · 2023-05-16 21:25:51 · 题解

思路

看到题目，首先第一眼想到暴力。

最朴素的暴力方法肯定是先枚举长度 i，再枚举左右端点，最后计算差值，这样的复杂度是 O(n^3) 的，肯定超时。

暴力代码：

#include <iostream>

using namespace std;
typedef long long ll;
#define int long long

int a[10101];

signed main(){
    int n;
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &a[i]);
    }
    for(int len = 1; len <= n; ++len){
        int l = 1, r = len;
        int cz = 1e15;
        while(r <= n){
            int L = l, R = r, nowcz = 0;
            while(L <= R){
                nowcz += abs(a[L] - a[R]);
                L++;
                R--;
            }
            ++l;++r;
            cz = min(cz, nowcz);
        }
        printf("%lld ", cz);
    }
    return 0;
}

接下来就是本篇的重点：优化（当然我也不会和你说什么 dp 和双指针之类的）。

我们不妨举个例子：

初始时假设 h = \{1,2,3,4,5,6,7\}，我们先将长度为 1 的算出来，很显然，都是 0，接下来不用着急算 i = 2 的情况，算 i = 3,5,7 的，我们会发现，在算其中的除了 l 和 r 端点外，其它的例如下标为 4 \sim 4 的啊，3 \sim 5 的都被之前给计算过了，于是我们大可开一个数组记录之前算过的差值，这样可以使得每次计算是 O(1) 的复杂度。

由于奇偶性不同，i 是偶数的情况也得分开记录差值。

复杂度是 O(n^2) 的，超时不了，还是目前的最优解。

#include <iostream>

using namespace std;
typedef long long ll;

ll h[10101];
ll a[10101], b[10101];

int main(){
    int n;
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &h[i]);
    printf("0 ");
    for(int i = 2; i <= n; ++i){
        if(i % 2 == 1){
            int l = n-i+1, r = n;
            ll cz = 1e15;
            while(r >= i){
                a[r] = a[r-1] + abs(h[r] - h[l]);
                cz = min(cz, a[r]);
                --l;--r;
            }
            printf("%lld ", cz);
        }else{
            int l = n-i+1, r = n;
            ll cz = 1e15;
            while(r >= i){
                b[r] = b[r-1] + abs(h[r] - h[l]);
                cz = min(cz, b[r]);
                --l;--r;
            }
            printf("%lld ", cz);
        }
    }
    return 0;
}