P1359 租用游艇

本题链接：P1359 租用游艇

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

输入格式
第一行中有一个正整数 n，表示有 n 个游艇出租站。接下来的 n−1 行是一个半矩阵 r(i,j)``（1≤i<j≤n）。

输出格式
输出计算出的从游艇出租站 1 到游艇出租站 n 所需的最少租金。

输入输出样例
输入
3
5 15
7

输出
12

说明/提示
n≤200，保证计算过程中任何时刻数值都不超过 1e6

本博客给出本题截图：

AC代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 210;

int n;
int f[N];       //从 1 ~ i 中的最少花费
int r[N][N];    //r[i][j]代表从 i ~ j 的花费

int main()
{
    cin >> n;
    for (int i = 1; i < n; i ++ )
        for (int j = i + 1; j <= n; j ++ ) 
            cin >> r[i][j];
    
    memset(f, 0x3f, sizeof f);
    f[1] = 0;  //从 1 ~ 1的花费显然是0
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j < i; j ++ ) 
            f[i] = min(f[i], f[j] + r[j][i]);
            
    cout << f[n] << endl;
    
    return 0;
}

  

 

  
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
 

总结

题目叙述很怪，输入样例中的大概含义是1~2花费5，1~3花费15，2~3花费7

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/119763053