矩阵选数

发布于 2023-03-10 | 分类于滚动数组、动态规划、 oi | 2分钟 | 353字数 | 浏览量：

题目描述

给定一个 $3$ 行， $n$ 列的矩阵，我们要在矩阵的每一列选一个数。对于第 $i(1 \le i \le n)$ 列，我们令 $d_i$ 为第 $i$ 列选择的数。那么， $\sum_1^{n-1}|d_i - d_{i+1}|$ 最小是多少

输入格式

第一行一个整数 $n$ ，描述见上文

后面三行每行 $n$ 个整数，为矩阵的各个元素

输出格式

一个整数，题目要求的最小值

测试样例

样例输入

样例输出

数据规模

对于 $100 \%$ 的数据， $1 \le n \le 10^6$ ，矩阵中数据绝对值不超过 $10^6$

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define ll long long
ll d[3][MAXN], n, dp[3][2];
inline ll min(const ll& a, const ll& b, const ll& c) {
    return std::min(std::min(a, b), c);
}

int main() {
    scanf("%lld", &n);
    for (ll i = 0; i < 3; ++i)
        for (ll j = 1; j <= n; ++j)
            scanf("%lld", &d[i][j]);
    for (ll i = 2; i <= n; ++i)
        for (ll j = 0; j < 3; ++j)
            dp[j][i % 2] = min(dp[0][(i - 1) % 2] + abs(d[j][i] - d[0][i - 1]), dp[1][(i - 1) % 2] + abs(d[j][i] - d[1][i - 1]), dp[2][(i - 1) % 2] + abs(d[j][i] - d[2][i - 1]));
    cout << min(dp[0][n % 2], dp[1][n % 2], dp[2][n % 2]);
}