HHR的小站
享受代码带来的快乐吧
首页
最新评论
您正在查看:2020年4月
2020-04-06 |HHR

问题描述:
长江游艇俱乐部在长江上设置了 n 个游艇出租站 1, 2, …, n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站 i 到游艇出租站 j 之间的租金为 r(i, j)(1≤i<j≤n)。试设计一个算法,计算出从游艇出租站 1 到游艇出租站 n 所需的最少租金。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> distance;
    for (int i = 1; i < n; i++) {
        vector<int> tmp;
        tmp.reserve(n);
        for (int j = 0; j < i; j++) {
            tmp.push_back(0);
        }
        for (int j = i; j < n; j++) {
            int t;
            cin >> t;
            tmp.push_back(t);
        }
        distance.push_back(tmp);
    }
    vector<int> ans = {0};
    for (int i = 1; i < n; i++) {
        int min = ans[i - 1] + distance[i - 1][i];
        for (int j = 0; j < i; j++) {
            min = min < ans[j] + distance[j][i] ? min : ans[j] + distance[j][i];
        }
        ans.push_back(min);
    }
    cout << ans[n - 1] << endl;
    return 0;
}

WordPress提供了很方便的CSS编辑器,可以为你的页面添加样式。
打开你的主题,进入“自定义CSS”,输入

html {
    filter: progid:DXImageTransform.Microsoft.BasicImage(grayscale=1);
    -webkit-filter: grayscale(100%);
}

即可让你的页面变成灰色

悼念逝者,致敬英雄