首页 > 试题广场 >

小强的神奇矩阵

[编程题]小强的神奇矩阵

热度指数：1586 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小强有一个 $3\times n$ 的矩阵 $\mathit a$ ，他将 $\mathit a$ 中每列的三个数字中取出一个按顺序组成一个长度为 $\mathit n$ 的数组 $\mathit b$ ，即 $b_i$ 可以是 $a_{1,i},a_{2,i},a_{3,i}$ 其中任意一个。问 $\sum_{i=1}^{n-1}\left|b_i-b_{i+1}\right|$ 的最小值是多少。

输入描述:

第一行，一个正整数。
第二行到第四行输入一个的矩阵，每行输入个正整数。
。

输出描述:

一行一个正整数表示答案。

示例1

输入

输出

说明

数组可以为，答案为。

算法知识视频讲解

pein531

利用动态规划求解，dp_ij表示选择a_ij作为b_j时，对于数组{b₁, b₂, ..., b_j}的最小目标值。当选择b_j时，需要穷举9种可能性，a_ij需要检查|a_ij-a_1j-1|+dp₁_j-1，|a_ij-a_2j-1|+dp₂_j-1，|a_ij-a_3j-1|+dp₃_j-1哪个最小（分别对应的是b_j固定为a_ij的情况下，b_j-1选的是a_1、a_2、a₃的三种情况），得到状态转移方程：

dp_ij=min(|a_ij-a₁_j-1|+dp₁_j-1，|a_ij-a_2j-1|+dp₂_j-1，|a_ij-a_3j-1|+dp₃_j-1)

遍历完成后，dp矩阵最后一列的最小值就是题目所求

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] arr = new long[3][n];
        for(int i = 0; i < 3; i++){
            String[] rawRow = br.readLine().trim().split(" ");
            for(int j = 0; j < n; j++)
                arr[i][j] = Long.parseLong(rawRow[j]);
        }
        long[][] dp = new long[3][n];
        for(int j = 1; j < n; j++){
            for(int i = 0; i < 3; i++){
                dp[i][j] = Math.min(Math.abs(arr[i][j] - arr[0][j - 1]) + dp[0][j - 1],
                                    Math.min(Math.abs(arr[i][j] - arr[1][j - 1]) + dp[1][j - 1],
                                             Math.abs(arr[i][j] - arr[2][j - 1]) + dp[2][j - 1]));
            }
        }
        System.out.println(Math.min(Math.min(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]));
    }
}

scala版本，不得不说scala在OJ上面的运行速度……真的好慢，刷题领域c++，java永远滴神

import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val n = StdIn.readInt()
        val dp = Array.ofDim[Long](3, n)
        val arr = Array.ofDim[Long](3, n)
        for(i <- 0 to 2){
            val rows = StdIn.readLine.trim.split(" ")
            for(j <- 0 to n - 1)
                arr(i)(j) = rows(j).toInt
        }
        for(j <- 1 to n - 1){
            for(i <- 0 to 2){
                // 在本次选i的情况下考虑上一次分别选0,1,2的情况
                dp(i)(j) = List[Long](math.abs(arr(i)(j) - arr(0)(j - 1)) + dp(0)(j - 1),
                                      math.abs(arr(i)(j) - arr(1)(j - 1)) + dp(1)(j - 1),
                                      math.abs(arr(i)(j) - arr(2)(j - 1)) + dp(2)(j - 1)).min
            }
        }
        println(List[Long](dp(0)(n - 1), dp(1)(n - 1), dp(2)(n - 1)).min)
    }
}

编辑于 2021-08-26 10:49:53 回复(1)

成长的程序员

#include <iostream>
#include <vector>
using namespace std;
void solution(int n)
{
    vector<vector<int>> nums(3,vector<int>(n, 0));
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> nums[i][j];
        }
    }
    vector<vector<long long>> dp(3, vector<long long>(n, 0));

    for (int j = 1; j < n; ++j)
    {
        for (int i = 0; i < 3; ++i)
        {
            long long f1 = abs(nums[i][j] - nums[0][j - 1]) + dp[0][j - 1];
            long long f2 = abs(nums[i][j] - nums[1][j - 1]) + dp[1][j - 1];
            long long f3 = abs(nums[i][j] - nums[2][j - 1]) + dp[2][j - 1];
            dp[i][j] = min(min(f1, f2), f3);
        }
    }
    cout << min(min(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]) << endl;
}

int main()
{
    int n = 0;
    cin >> n;
    solution(n);
    return 0;
}

发表于 2021-08-14 23:33:41 回复(0)

Python

O_n2

动态规划

def compute(matrix, n):
    dp_matrix = [[0, 0, 0]]
    for j in range(1, n):
        delta_i = []
        for i in range(3):
            d0 = abs(matrix[i][j] - matrix[0][j-1]) + dp_matrix[-1][0]
            d1 = abs(matrix[i][j] - matrix[1][j-1]) + dp_matrix[-1][1]
            d2 = abs(matrix[i][j] - matrix[2][j-1]) + dp_matrix[-1][2]
            delta_i.append(min(d0, d1, d2))
        dp_matrix.append(delta_i)
    print(min(dp_matrix[-1]))

编辑于 2021-04-29 14:32:54 回复(0)

kiyoxi

类似于求图的最短路径问题，可以利用dijistra算法求解

import sys

n = int(sys.stdin.readline().strip())
data = []
for _ in range(3):
    data.append([int(i) for i in sys.stdin.readline().strip().split(' ')])
last = [0]*3
i = 1
while(i<n):
    last1 = [0]*3
    for j in range(3):
        last1[j] = min([abs(data[k][i-1]-data[j][i])+last[k] for k in range(3)])
    last = last1
    i+=1
print(min(last))

发表于 2021-08-03 16:03:52 回复(0)

不想看论文

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int[][] a = new int[3][n];
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < n; j++){
                a[i][j] = cin.nextInt();
            }
        }
        long[][] dp = new long[3][n];
        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                long d0 = Math.abs(a[j][i] - a[0][i - 1]) + dp[0][i - 1];
                long d1 = Math.abs(a[j][i] - a[1][i - 1]) + dp[1][i - 1];
                long d2 = Math.abs(a[j][i] - a[2][i - 1]) + dp[2][i - 1];
                dp[j][i] = Math.min(Math.min(d0, d1), d2);
            }
        }
        System.out.println(Math.min(Math.min(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]));
    }
}

发表于 2022-03-27 10:31:59 回复(0)

爆爆只是想帮忙

#include<bits/stdc++.h>
using namespace std;
//动态规划
long helper(vector<vector<int>>& nums, int n){
    //dp[i][j]:到第j列为止，选择nums[i][j]为结尾的最小值
    vector<vector<long>> dp(3, vector<long>(n));
    for(int j = 1; j < n; j++){
        for(int i = 0; i < 3; i++){
            long path1 = dp[0][j - 1] + abs(nums[0][j - 1] - nums[i][j]);
            long path2 = dp[1][j - 1] + abs(nums[1][j - 1] - nums[i][j]);
            long path3 = dp[2][j - 1] + abs(nums[2][j - 1] - nums[i][j]);
            dp[i][j] = min(min(path1, path2), path3);
        }
    }
    return min(dp[0][n - 1], min(dp[1][n - 1], dp[2][n - 1]));
}

int main(){
    int n;
    while(cin >> n){
        vector<vector<int>> nums(3, vector<int>(n));
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < n; j++){
                cin >> nums[i][j];
            }
        }
        cout << helper(nums, n) << endl;
    }
}

发表于 2022-03-13 14:58:29 回复(0)

中南大学李彬

#include<iostream>
#include<bits/stdc++.h>
#include<limits>
#include<vector>
typedef unsigned long long ll;
using namespace std;
ll Min(ll a,ll b)
{
    if(a>=b) return b;
    else return a;
}
ll Abs(ll a,ll b)
{
    if(a>b) return a-b;
    else return b-a;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    ll n;
    cin>>n;
    ll a[3][n];
    for(int i=0;i<3;i++)
    {
        for(ll j=0;j<n;j++)
            cin>>a[i][j];
    }
    vector<vector<ll>> dp(3,vector<ll> (n-1,LONG_LONG_MAX));
    // int dp[3][n-1];
    // memset(dp,INT_MAX,3*(n-1));
    //边界条件
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            dp[i][0]=Min(dp[i][0],Abs(a[j][0],a[i][1]));
        }
    }
    //代价矩阵
    for(ll j=1;j<n-1;j++)
    {
        for(int i=0;i<3;i++)
        {
            for(int k=0;k<3;k++)
            {
                dp[i][j]=Min(dp[i][j],dp[k][j-1]+Abs(a[k][j],a[i][j+1]));
            }
        }
    }
    ll ans=dp[0][n-2];
    for(int i=1;i<3;i++)
    {
        ans=Min(ans,dp[i][n-2]);
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2021-06-03 15:55:55 回复(0)

有一个地方.

n = int(input())
arr = []
for i in range(3):
    arr.append(list(map(int, input().split())))
#dp[i][j] 前i个元素，第i个元素取第j个的最小值 return min(dp[n][j])(j=0, 1, 2)
dp = [[float("inf")] * 4 for _ in range(n + 1)]
tmp = [arr[0][0], arr[1][0], arr[2][0]]
for i in range(3):
    for j in range(3):
        dp[2][i + 1] = min(dp[2][i + 1], abs(arr[i][1] - arr[j][0]))
for i in range(3, n + 1):
    for j in range(1, 4):
        for k in range(1, 4):
            dp[i][j] = min(dp[i][j], abs(arr[j - 1][i - 1] - arr[k - 1][i - 2]) + dp[i - 1][k])
ans = float("inf")
for i in range(1, 4):
    ans = min(ans, dp[n][i])
print(ans)

编辑于 2021-05-06 13:19:17 回复(0)