租用游艇问题

问题描述：

长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租

站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间

的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需

的最少租金。

&laquo;编程任务：

对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i<j<=n，编程计算从

游艇出租站1 到游艇出租站n所需的最少租金。

&laquo;数据输入：

由文件input.txt 提供输入数据。文件的第1 行中有1 个正整数n（n<=200），表示有n

个游艇出租站。接下来的n-1 行是r(i,j),1<=i<j<=n。

&laquo;结果输出:

程序运行结束时，将计算出的从游艇出租站1 到游艇出租站n所需的最少租金输出到文

件output.txt中。

输入文件示例 输出文件示例

input.txt

3

5 15

7

output.txt

12

分析，类似矩阵连乘，可参看矩阵连乘问题：

 

#include
      
        #include
       
         using namespace std; #define N 202 int p[N][N]; int main() {
    int n,i,j,k,r; while(scanf("%d",&n)!=EOF)     {
    for(i=1;i<=n-1;i++)         {
    for(j=i+1;j<=n;j++)                 scanf("%d",&p[i][j]);         } for(r=2;r<=n;r++)         {
    for(i=1;i<=n-r+1;i++)             {
                    j=i+r-1; for(k=i+1;k