租用游艇问题

租用游艇问题

时间： 1ms        内存：64M

描述：

长江游艇俱乐部在长江上设置了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i

输入：

输入数据的第1 行中有1 个正整数n（n<=200），表示有n个游艇出租站。接下来的n-1 行是r(i,j),1≤i

输出：

输出一个整数，表示计算出的从游艇出租站1 到游艇出租站n所需的最少租金。

示例输入：

3
5 15
7

示例输出：

12

提示：

参考答案（内存最优[1424]）：

#include<iostream>
using namespace std;
#define N 201
int f[N][N];
int n;
void init()
{
       int i,j;
       for(i=0;i<n;i++)
              for(j=0;j<n;j++) f[i][j]=0;
       for(i=0;i<n-1;i++)
              for(j=i+1;j<n;j++) cin>>f[i][j];
}
void dyna()
{
       for(int k=2;k<n;k++)
              for(int i=0;i<n-k;i++)
              {
                     int j=i+k;
                     for(int p=i+1;p<j;p++)
                     {
                            int temp=f[i][p]+f[p][j];
                         if(f[i][j]>temp) f[i][j]=temp;
                     }
              }
}
int main()
{
       cin>>n;
    init();
       dyna();
       cout<<f[0][n-1]<<endl;
       return 0;
}

参考答案（时间最优[8]）：

#include<iostream>
#include<string.h>
using namespace std;
#define N 201
int f[N][N];
int n;
void init()
{
    int i,j;
    memset(f,0,sizeof(f));
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            cin>>f[i][j];
}
void dyna()
{
    for(int k=2; k<n; k++)
        for(int i=0; i<n-k; i++)
        {
            int j=i+k;
            for(int p=i+1; p<j; p++)
            {
                int temp=f[i][p]+f[p][j];
                if(f[i][j]>temp)f[i][j]=temp;
            }
        }
}
int main()
{
    cin>>n;
    init();
    dyna();
    cout<<f[0][n-1]<<endl;
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。