#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <unordered_set>
using namespace std;
int getRes(vector<int> v, int a, int b, int c) {
int n = v.size();
vector<vector<int> > dp(n, vector<int>(n, n));
for (int i = 0; i < n; i++) {
dp[i][i] = 0;
}
for (int i = n - 1; i >= 0;i--) {
for (int j = 0; j < n; j++) {
if (v[i] > 1) dp[i][j] = min(dp[i][j], dp[i][v[i] - 1] + dp[v[i] - 1][j] + b);
else if (v[i] < n) dp[i][j] = min(dp[i][j], dp[i][v[i] + 1] + dp[v[i] + 1][j] + c);
else dp[i][j] = min(dp[i][v[i]] + dp[v[i]][j] + a, dp[i][j]);
}
}
return dp[0][n - 1];
}
int main() {
vector<int> v = { 3,6,4,3,4,5,6 };
int res = getRes(v, 1, 1, 1);
cout << res << endl;
return 0;
}
用动规的思想来做，不过状态转移方程式和初始化顺序有些问题，0AC，还请大佬帮忙解答。dp[i][j]代表从城市i到城市j的最小花费。
#度小满##笔试题目#
查看1道真题和解析
