/* ? 問題描述 長江游艇俱樂部在長江上設(shè)置了n個(gè)游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1?i<j?n。試設(shè)計(jì)一個(gè)算法，計(jì)算出從游艇出租站1到游艇出租站n所需的最少租金。計(jì)算從首站到末站的最小費(fèi)用 第一行數(shù)字表示有n個(gè)站點(diǎn) 后邊的第x行第y列的數(shù)字表示從第x站到第x+y站的費(fèi)率 輸入文件示例 輸出文件示例 input.txt output.txt 3 5 15 12 7 input.txt output.txt 4 15 3 7 19 5 13 8*/#include<iostream> #include<fstream> #include<string>using namespace std; //在測試條件下最大值設(shè)置為6已經(jīng)夠用 //也可以更大 const int max = 6;//參數(shù)begin、end代表索引（index），從0開始而非從1開始 //參數(shù)begin、end分別為要求解的起始站點(diǎn)和最終站點(diǎn)的索引 //使用dp[x][y]存儲(chǔ)從x到y(tǒng)的最小費(fèi)用 //使用port[x][y]存儲(chǔ)題目給出的直接從x到y(tǒng)的價(jià)格， //實(shí)際上dp與port都只用了一個(gè)三角矩陣，但為了方便還是分配整個(gè)矩陣的空間 //返回值僅對(duì)于最上層的調(diào)用有意義，內(nèi)部的遞歸調(diào)用的返回值沒有用處 //事實(shí)上也可以不要返回值，因?yàn)榉祷刂稻驮赿p[begin][end]中，可以取出 int solve(int dp[max][max], int port[max][max], int end, int begin) {//臨時(shí)變量，為了VC中調(diào)試時(shí)鼠標(biāo)指上去觀察數(shù)值，實(shí)際上可以不要int ret = -1;//從站點(diǎn)出發(fā)到自身，不花錢，記錄在dp中if (begin == end) {dp[begin][end] = 0;ret = dp[begin][end];return 0;}//如果兩站相鄰，則直接到達(dá)的費(fèi)用就是最小費(fèi)用，記錄在dp中else if (begin == end - 1) {dp[begin][end] = port[begin][end];ret = dp[begin][end];return dp[begin][end];}//如果兩站相隔較遠(yuǎn)，則比較麻煩//出發(fā)站到末站的最小費(fèi)用是直接到達(dá)和經(jīng)過其他站轉(zhuǎn)到的各種情況的費(fèi)用中最小的那個(gè)//A到D的最小費(fèi)用為min（A到B的最小費(fèi)用+B到D的最小費(fèi)用，//A直接到C 的最小費(fèi)用+C到D的最小費(fèi)用，A直接到D的最小費(fèi)用）else if (end - begin > 1) {int min = port[begin][end]; //直接到達(dá)的費(fèi)用總是已知的//用一個(gè)循環(huán)遍歷查找最小值for (int i = 1; i < end - begin; i++) {//如果中轉(zhuǎn)站到末站的費(fèi)用還是未知，則先遞歸算出來再使用if (dp[begin + i][end] == -1) {solve(dp, port, end, begin + i);}//如果起始站到中轉(zhuǎn)站的費(fèi)用還是未知，則先遞歸算出來再使用if (dp[begin][begin + i] == -1) {solve(dp, port, begin + i, begin);}//如果到某個(gè)中轉(zhuǎn)站的費(fèi)用更小，則把最小值更新為這個(gè)費(fèi)用if (min > dp[begin + i][end] + dp[begin][begin + i]) {min = dp[begin + i][end] + dp[begin][begin + i];}}//把最小費(fèi)用填入表格，以供使用dp[begin][end] = min;}else {//其他情況提示出錯(cuò)cout << "ERROR!" << endl;getchar();getchar();exit(-1);}//現(xiàn)實(shí)計(jì)算結(jié)果以便檢查，并返回cout << dp[begin][end] << endl;return dp[begin][end]; }int main() {//讀取文件 fstream fs;fs.open("input.txt", ios::in);int n; //站點(diǎn)數(shù)量int dp[max][max]; //存放任意兩站之間的最小費(fèi)用的表int port[max][max]; //存儲(chǔ)初始信息，各站點(diǎn)直達(dá)其他站點(diǎn)的費(fèi)用 fs >> n;cout << n << endl;//初始化，以-1為空值for (int i = 0; i < n; i++){for (int j = 0; j < n; j++) {dp[i][j] = -1;port[i][j] = -1;}}//讀取并儲(chǔ)存第x站到第y站的費(fèi)率for (int i = 0; i < n - 1; i++) {for (int j = i + 1; j < n; j++) {fs >> port[i][j];cout << port[i][j] << '\t';}cout << endl;}//結(jié)束讀取，關(guān)閉文件 fs.close();int ret = solve(dp, port, n - 1, 0);//結(jié)果寫入到文件fs.open("output.txt", ios::out);fs << ret;fs.close();cout << ret << endl;cout << "Finish" << endl;cin >> n;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/memoryLost/p/10629534.html

總結(jié)

以上是生活随笔為你收集整理的计算首站到末站最小费用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。