2617: 动态规划-游艇问题
金币值：3
定数：7
时间限制：1.000 s
内存限制：128 M
正确：4
提交：4
正确率：100.00% 命题人：
题目描述
长江游艇俱乐部在长江上设置了 $n$ （$n<=10$）个游艇出租站 $1，2，…，n$。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 $i$ 到游艇出租站 $j$ 之间的租金为 $r$($i,j$),$1≤i＜j≤n$。要求设计一个算法，计算出从游艇出租站 $1$ 到游艇出租站 $n$ 所需的最少租金（使用动态规划法）。
要求：
第 $1$ 行输入 $1$ 个整数，表示有n个出租站点。
第 $2$ 行输入 $n-1$ 个整数，依次表示第1个站点到第 $i$（$1<i\le n$）个站点的租金。
第 $3$ 行输入 $n-2$ 整数，依次表示第2个站点到第 $i$（$2<i\le n$）个站点的租金。
...
第 $n$ 行输入 $1$ 整数，依次表示第 $n-1$ 个站点到第 $i$（$n-1<i\le n$）个站点的租金。
最后 $1$ 行直接输出第1个出租点到第 $n$ 个出租点的最小租金。
要求：
第 $1$ 行输入 $1$ 个整数，表示有n个出租站点。
第 $2$ 行输入 $n-1$ 个整数，依次表示第1个站点到第 $i$（$1<i\le n$）个站点的租金。
第 $3$ 行输入 $n-2$ 整数，依次表示第2个站点到第 $i$（$2<i\le n$）个站点的租金。
...
第 $n$ 行输入 $1$ 整数，依次表示第 $n-1$ 个站点到第 $i$（$n-1<i\le n$）个站点的租金。
最后 $1$ 行直接输出第1个出租点到第 $n$ 个出租点的最小租金。
测试代码 复制
#include <stdio.h>
int m[11][11]; // 假设下标为0的位置不存储有效数据
int f(int n) {
int i,j,k,p;
for(i=1; i<=n; i++) m[i][i]=0; // 给主对角线(第1条对解线)赋值
___________________________
return m[1][n];
}
int main(void) {
int i,j,n,result;
scanf("%d",&n);
for(i =1; i < n; i++ )
for(j =i+1; j <= n; j++ )
scanf("%d",&m[i][j]);
result=f(n);
printf("%d\n",result);
return 0;
}输入样例 复制
5
2 4 6 8
1 2 3
1 2
3输出样例 复制
5提示
算法设计思路：先写出计算 $m[i][j]$ 值的递归式，然后根据递归式设计动态规划算法。
另外，如果本题不用动态规划，而是直接利用递归求解，则可参考下列程序代码（当问题规模比较大时，该代码的执行效率较低）
另外，如果本题不用动态规划，而是直接利用递归求解，则可参考下列程序代码（当问题规模比较大时，该代码的执行效率较低）
#include <stdio.h>
int m[11][11]; // 假设下标为0的位置不存储有效数据
int f(int i, int j) {
if(i==j) {
return 0;
}else{
int min=m[i][j];
for(int k=i+1; k<j; k++) {
_______________
}
return min;
}
}
int main(void) {
int i,j,n,result;
scanf("%d",&n);
for(i =1; i < n; i++ )
for(j =i+1; j <= n; j++ )
scanf("%d",&m[i][j]);
result=f(1,n);
printf("%d\n",result);
return 0;
}