租用游艇问题

[效云 李]

租用游艇问题

Description

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

编程任务：
对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i
游艇出租站1 到游艇出租站n所需的最少租金。

Input

由文件input.txt 提供输入数据。文件的第1 行中有1 个正整数n（n<=200），表示有n
个游艇出租站。接下来的n-1 行是r(i,j),1<=i< font>

Output

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

Sample Input

3
5 15
7

Sample Output

12

[效云 李]

// 动态规划-租用游艇问题.cpp : Defines the entry point for the console
application.
//这题的动态规划思想和前几题几乎一模一样，略做改动的也就是，在按步求出最优值的时候由于有游艇直接到达，要与原始数据比较一下，得出最优值 输
入输出均以txt的形式

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
int n=0;
ifstream finput;
finput.open("input.txt");
finput>>n;

vector<vector<int> > m_old(n+1,vector<int>(n+1));
vector<vector<int> > m_new(n+1,vector<int>(n+1));

int i=0,j=0,temp=0;
for(i=1;i<n;++i)
{
for(j=i+1;j<=n;++j)
{
finput>>temp;
m_old[i][j]=temp;
}
}

void (*p)(vector<vector<int> > ,vector<vector<int> >&,int);
void calculate(vector<vector<int> > ,vector<vector<int> >&,int);
p=calculate;
(*p)(m_old,m_new,n);

ofstream foutput;
foutput.open("output.txt");
foutput<<m_new[1][n]<<endl;

return 0;
}

void calculate(vector<vector<int> > m_old ,vector<vector<int> >&
m_new,int n)
{
for(int step=1;step<n;++step) //步长
{
for(int i=1;i<=n-step;++i) //起点
{
int j=i+step; //结尾
m_new[i][j]=m_old[i][j];//初始化m_new[i][j],采用m_old[i][j]
for(int k=i+1;k<j;++k)
{
if(m_new[i][j]>(m_new[i][k]+m_new[k][j])) m_new[i][j]=(m_new[i][k]
+m_new[k][j]);