将序列 b 的价值拆为两部分, 第一部分为 序列 a 与 序列 b 对应位之差

第二部分为序列 b 相邻位差的平方

显然, 这两部分都可以分配到每一个元素头上, 即计算每一个元素 b[i] 的贡献值

由于 a[i] 取值在 [0, 9], 当 b[i] 在这个区间之外时, 显然会使第一部分过大

而第二部分与 b[i] 的取值范围无关

故最优解的 b[i] 一定在 [0, 9] 区间内

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 1e5 + 20;
int n, q[N], f[N][10];

// b[i] 取 y, b[i - 1] 取 x 时, 第 i 位的贡献
int check(int i, int x, int y)
{
    if(i == 1) return abs(q[i] - y);
    return abs(q[i] - y) + (x - y) * (x - y);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    // 初始化
    memset(f, 0x3f, sizeof(f));
    for(int i = 0; i < 10; i ++)
    {
        f[0][i] = 0;
    }

    for(int i = 1; i <= n; i ++)
    {
        cin >> q[i];
        for(int j = 0; j < 10; j ++)
        {
            for(int k = 0; k < 10; k ++)
            {
                f[i][j] = min(f[i][j], f[i - 1][k] + check(i, k, j));
            }
        }
    }

    int ans = 0x3f3f3f3f;
    for(int i = 0; i < 10; i ++)
    {
        ans = min(ans, f[n][i]);
    }

    cout << ans;
}