学步园

问题描述

   某旅游城市在长江边开辟了若干个旅游景点。一个游船俱乐部在这些景点都设置了游艇出租站。游客可在这些游船出租站租用游船，并在下游的任何一个游船出租站归还游船，从一个游船出租站到下游的游船出租站间的租金明码标价。你的任务是为游客计算从起点到终点站间的最小租船费用。

输入

    输入文件有若干组数据，每组测试数据的第一行上有一个整数n(1<=n<=100)，表示上游的起点站0到下游有n个游船出租站

1，2，。。。，n。接下来有n行，这n行中的第1行有n个整数，分别表示第0站到第1，2，3，。。。，n站间的游船租金；第2行有n-1个整数，分别表示第1站到第2，3，4，。。。n站间的游船租金；。。。。；第n-1行有2个整数，表示第n-2站到第n-1、n站间的游船租金；第n行有1个整数，表示第n-1站到第n站间的游船租金。一行上有两个整数之间是用空格隔开的。两组测试数据之间无空行。

输出

    对输入文件中的每组测试数据，先在一行上输出“Case #:”，其中“#”测试数据的编号（从1开始）。再输出一行，内容是该情况下游客从起点站到终点站间的最少租船费用。

输入样例

3

2 3 6

1 3

2

输出样例

Case 1:

5

此题是动态规划一个入门题。

分析：

   设mincost[j] 为起始点到j点所花费用的值的最小值

   那么动态方程就是

mincost[i] = min{mincost[j] + cost[j][i]};其中i为当前的站点，j>=0&&j<i;

cost[j][i] 表示j点到i点的所花的费用。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<climits>
using namespace std;
int main()
{
   int cost[100][101];
   int mincost[101];
   int n;
   memset(cost,0,sizeof(cost));
   cin >> n;
   
   for(int i = 0;i < n; i++)
      for(int j = i + 1; j <= n; j++)
       cin >> cost[i][j];
       
   /* for(int i = 0;i < n; i++)
      for(int j = 0; j <= n; j++)
        j == n ?cout << cost[i][j] << " "<< endl:cout << cost[i][j] << " "; 
    */
   mincost[0] = 0;
   for(int i = 1; i < n+1; i++)
   mincost[i] = LONG_MAX;
   
   for(int i = 1; i <= n; i++)
      for(int j = 0; j < i; j++)
       if(mincost[j] + cost[j][i] < mincost[i])mincost[i] = mincost[j] + cost[j][i];
   cout << endl << mincost[n];
    system("pause");
}