PTA 租用游艇问题

题目描述

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

输入格式:

第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的第1到第n-1 行，第i行表示第i站到第i+1站,第i+2站, … , 第n站的租金。

输入样例:

1
2
3
3
5 15
7

输出样例:

1
12

题解:

我们可以想到如果要求第1个站到第n站的租金最小值,所可以$O(N^2)$枚举1->n站之间所有可能的情况——比如从第1个站到第3个站可以直接从第1个站到第3个站，也可以从第1个站先到第2个站再从第2个站到第3个站.所以我们需要用一个数组$dp[i][j]$记录第i个站到第j个站的最小租金,不断通过枚举更新这个数组,最终$dp[1][n]$就是第1个站到第n个站的最小租金,也就是我们要求的答案.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
using namespace std;
int r[205][205];//r[i][j]定义是从第i个站到第j个站的租金值
int dp[205][205];//dp[i][j]定义是从第i个站到第j个站的租金最小值

int main() {
    memset(dp, 0x3f, sizeof dp);//初始化dp数组，因为我们要求的是租金最小值，所以将dp数组全部初始化为一个很大的值
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> r[i][j];
            dp[i][j] = r[i][j];//初始化dp数组 从第i个站到第j个站的值先初始为r[i][j]
        }
    }
    for (int j = 2; j <= n; j++) {
        for (int k = 2; k < j; k++) {
            dp[1][j] = min(dp[1][j], dp[1][k] + dp[k][j]);//对于1->n之间所有的站两两之间都枚举所有情况然后取其最小值
            //比如从第1个站到第3个站可以直接从第1个站到第3个站，也可以从第1个站先到第2个站再从第2个站到第3个站
        }
    }
    //因为所有站两两之间的租法全部遍历过了，所以保证了结果的正确性

    cout << dp[1][n];//根据题意我们要求的是第1个站到第n个站的租金最小值，所以dp[1][n]为所求，输出即可

    return 0;
}