租用游艇问题

租用游艇问题2010-06-0917:48长江游艇俱乐部在长江上设置了n个游艇出租站1，2……n。游客可在游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站为r元（下文有解释），计算出游艇1到游艇n所需最少租金。输入：第一行有一个正整数n，表示n个游艇出租站。接下来n-1行为租金。如：35（出租站1到出租站2的租金)15(出租站1到出租站3的租金）7（出租站2到出租站3的租金）输出：12（最少租金）此题其实很简单，跟矩阵连乘相似，这里就不再作介绍了#includestdio.h#includestdlib.hmain(){intnum,**array,i,j,k,l;printf(请输入站点数\n);scanf(%d,&num);array=(int**)malloc((num+1)*sizeof(int*));for(i=1;i=num;i++)array[i]=(int*)malloc((num+1)*sizeof(int*));for(i=1;i=num;i++)array[i][i]=0;for(i=1;inum;i++)for(j=i+1;j=num;j++){printf(请输入从站点%d到站点%d的金额,i,j);scanf(%d,&array[i][j]);}for(i=2;i=num;i++)for(j=i+1;j=num;j++){k=j-i;for(l=k;lj;l++)if(array[k][l]+array[l][j]array[k][j])array[k][j]=array[k][l]+array[l][j];}printf(%d,array[1][num]);}