租用游艇问题
如题：
思路：
类似于矩阵连乘问题
从第i站到第j站时，我们可以从这两个站中间选择一个中间站k，先从始发站i坐从中间站k下船后，再从第k站坐船到第j站，这样就把一个大问题m[i][i]划分成了m[i][k]和m[k][j]两个子问题。
m[i][j]可以定义为
i+1==j, m[i][j]
i+1<j, min{ min(m[i][k]+m[k][j]), m[i][j] }
举例说明，
| 上站 | 下站 | 租金 |
|---|---|---|
| 1 | 2 | 5 |
| 1 | 3 | 15 |
| 1 | 4 | 21 |
| 2 | 3 | 7 |
| 2 | 4 | 14 |
| 3 | 4 | 8 |
m[i][j]
| m(1,1)=0 | m(1,2)=5 | m(1,3)=min{m(1,2) +m(2,3), m(1,3)}=12 | m(1,4)=min{m(1,2) +m(2,3) +m(3+4), m(1,4) }=20 |
|---|---|---|---|
| m(2,2)=0 | m(2,3)=7 | m(2,4)=min{m(2,3) +m(3,4), m(2,4)}=14 | |
| m(3,3)=0 | m(3,4)=8 | ||
| m(4,4)=0 |
for(int i = n; i >=1; i--){
for(int j = i+1; j <= n; j++){
for(int k = i+1; k < j; k++){
int temp = m[i][k] + m[k][j];
if(temp < m[i][j]){
m[i][j] = temp;
}
}
}
}
-
第一次循环：
i=3，j=4，不满足j<= n=3的条件，退出内层循环。 -
第二次循环：
i=2，j=1，不满足j>=i+1的条件，退出内层循环。 -
第三次循环：
i=1, j=3, k=2temp = m[1][2] + m[2][3] = 5 + 7 = 12temp小于m[1][3]的初始值 15，所以m[1][3]的值被更新为 12。
代码：
#include<stdio.h>
void calculateMinRent(int n, int m[100][100]){
//初始化
for(int i = 0; i < n; i++){
m[i][i] = 0;
}
//输入各个站点之间的租金
for(int i = 1; i <= n; i++){
// i 站点的下一个站点 i+1
for(int j = i+1; j <= n; j++){
scanf("%d", &m[i][j]);
}
}
//遍历矩阵的上半部分
//最外层循环从最后一站往前 控制行 (起始站点)
//第二层循环从当前站点往后 控制列 (当前站点的下一站点到终点站)
//第三次循环，划分区间，计算租金
for(int i = n; i >=1; i--){
for(int j = i+1; j <= n; j++){
for(int k = i+1; k < j; k++){
int temp = m[i][k] + m[k][j];
if(temp < m[i][j]){
m[i][j] = temp;
}
}
}
}
printf("%d\n", m[1][n]);
}
int main(){
int m[100][100];
int n;
scanf("%d", &n);
calculateMinRent(n,m);
return 0;
}