题解 | #最小花费#

解题思路：

dfs(i,j):表示从i站到j站的最少花费

从i到j有两种方法：

（1）如果i到j站之间距离小于l3则可之间前往

（2）如果大于l3，则尝试选取一个中转站k,将dfs(i,j）问题转换为子问题dfs(i,k)和dfs(k,j)，枚举每一个k,k的范围是i<k<j

最终递推公式为

dfs(i,j)=min(prices(i,j),min(dfs(i,k)+dfs(k,j)))

再在回溯的基础上增加记忆化搜索

#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;


int main() {
    int l1, l2, l3;
    int c1, c2, c3;
    while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) {
        int startStation, endStation;
        cin >> startStation >> endStation;
        int n;
        cin >> n;
        vector<int> stationsLength(n, 0);
        stationsLength[0] = 0;
        for (int i = 1; i < n; i++) {
            cin>>stationsLength[i];
        }

        function<int(int)> getPrice = [&] (int len) -> int{
            return len > l3 ? INT_MAX : (len > l2 ? c3 : ( len > l1 ? c2 : c1));
        };


        vector<vector<int>> dp(n, vector<int>(n, -1));

        function<int(int, int)> dfs = [&] (int i, int j) -> int{
            if (i==j) {
                return 0;
            }
            if (dp[i][j] == -1) {
                dp[i][j] = getPrice(stationsLength[j] - stationsLength[i]);
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = min(dp[i][j], dfs(i, k) + dfs(k, j));
                }
            }
            return dp[i][j];
        };


        /*vector<vector<int>> dp(n,vector<int>(n,INT_MAX));

        for (int i=n-1; i>=0; i--) {
            dp[i][i]=0;
            for (int j=i+1; j<n; j++) {
                dp[i][j]=getPrice(stationsLength[j]-stationsLength[i]);
                for (int k=i+1; k<j; k++) {
                    dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]);
                }


            }
        }*/


        cout << dfs(startStation - 1, endStation - 1) << endl;
    }
}
// 64 位输出请用 printf("%lld")

}// 64 位输出请用 printf("%lld")