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) } }
#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; }
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]))
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))
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])); } }
#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; } }
#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; }
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)