資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究C++ 程式，找出遊遍所有給定座標的費用
假設，我們得到了 n 個三維座標。從座標 (a, b, c) 到 (x, y, z) 的移動成本是 ∣ x − a∣ + ∣ y − b∣ + max(0, z − c)。我們從第一個座標開始，然後至少訪問所有座標一次，然後返回第一個座標。我們必須算出整個行程的總成本。這些座標在陣列 'coords' 中提供給了我們。
因此，如果輸入是 n = 3，coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}，則輸出將為 12。
為了解決這個問題，我們將按照以下步驟進行 −
Define one 2D array tpa. tpa[1, 0] := 0 for initialize i := 1, when i < 2n, update (increase i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: if i mod 2 is same as 0, then: Ignore following part, skip to the next iteration for initialize t := 0, when t < n, update (increase t by 1), do: x := first value of coords[t] y := second value of coords[t] z := third value of coords[t] p := first value of coords[j] q := second value of coords[j] r := third value of coords[j] tpa[i OR (1 bitwise left shift t)][t] := minimum of (tpa[i|(1 bitwise left shift t)][t], tpa[i][j] + |x - p| + |y - q| + maximum of (0, z - r)) res := infinity for initialize i := 0, when i < n, update (increase i by 1), do: x := first value of coords[0] y := second value of coords[0] z := third value of coords[0] p := first value of coords[i] q := second value of coords[i] r := third value of coords[i] res := minimum of (res and tpa[2n - 1, i] + |x - p| + |y - q| + maximum of (0 and z - r)) return res
示例
讓我們看看以下實現，以獲得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
int solve(int n, vector<tuple<int,int,int>> coords){
vector<vector<int>> tpa(pow(2, n), vector<int>(n, INF));
tpa[1][0] = 0;
for(int i = 1; i < pow(2,n); i++) {
for(int j = 0; j < n; j++){
if(i % 2 == 0)
continue;
for(int t = 0; t < n; t++) {
int x, y, z, p, q, r;
tie(x, y, z) = coords[t];
tie(p, q, r) = coords[j];
tpa[i | (1 << t)][t] = min(tpa[i|(1 << t)][t], tpa[i][j] + abs(x - p) + abs(y - q) + max(0, z - r));
}
}
}
int res = INF;
for(int i = 0; i < n; i++) {
int x, y, z, p, q, r;
tie(x, y, z) = coords[0];
tie(p, q, r) = coords[i];
res = min(res, tpa[pow(2, n) - 1][i] + abs(x - p) + abs(y - q) + max(0, z - r));
}
return res;
}
int main() {
int n = 3;
vector<tuple<int,int,int>> coords = {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}};
cout<< solve(n, coords);
return 0;
}輸入
3, {{1, 1, 0}, {1, 3, 4}, {3, 2, 2}}輸出
12
更新於: 2022 年 2 月 25 日
205 次瀏覽
廣告