租用游艇问题

租用游艇问题

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注