租用游艇

题目描述

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

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 个游艇出租站。接下来的 $n-1$ 行是一个半矩阵 $r(i,j)$（$1\le i<j\le n$）。

输出格式

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

样例 #1

样例输入 #1

1
2
3
3
5 15
7

样例输出 #1

1
12

提示

$n\le 200$，保证计算过程中任何时刻数值都不超过 $10^6$。

题解

题目解析

题目给的数据是这个意思:

中转站1 中转站2 中转站3
中转站1 0 5 15
中转站2 0 0 7
中转站3 0 0 0

用二维数组存下来就是:

1
a[i][j] := 从中转站i到中转站j需要的租金

接下来就需要我们考虑如何构造状态转移方程了:

  • 构造dp数组: dp[i] := 到达i中转站所需要的最少租金

分析一下他们之间的状态转移关系:

1
2
3
4
5
6
dp[i]究竟是如何得到:
	dp[i] = min(a[j][i] + dp[j], dp[i])
怎么解释:
	从1到达i中转站所需要的最少租金 = min(从j到i的租金 + 从1到达j中转站所需要的最少租金 , 从1到达i中转站所需要的最少租金)
j怎么取值呢?
	j需要从1取到i-1.

我们再分析一下上面的数据表格,我们会发现dp有初始值: 1->2,1->3都有值,我们就可以把dp[i]赋初值了

AC代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(200);
int a[MAXN][MAXN],dp[MAXN];

signed main(){
    int n;
    cin >> n;
    fa(1,n-1,1){
    	for(int j=i+1;j<=n;j++){
    		cin >> a[i][j];
    		if(i == 1) dp[j] = a[i][j];//给从1直接到i赋初值
    	}
    }
    dp[1] = 0;//自己到自己肯定为0
    fa(2,n,1){
    	for(int j=i-1;j>=1;j--){
    		dp[i] = min(dp[i],a[j][i]+dp[j]);
    	}
    }
    cout << dp[n] << endl;
    return 0;
}