游艇租用

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


试设计一个算法，计算从游艇出租站1到游艇出租站n所需的最少租金。


Input
第 1 行中有 1 个正整数 n（n<=200） ，表示有 n个游艇出租站。


接下来的n-1 行是r(i,j),  r(i,j)为整数，1 ≤ i < j ≤ n。 


Output
输出从游艇出租站1到游艇出租站n所需的最少租金。


Sample Input
3
5 15
7
Sample Output
12


dp(i,j)表示从i到j的最小花费
则状态转移方程 dp(i,j) = min(dp(i,j),dp(i)(k)+dp(k)(j)) ;其中 i<k<j


#include <bits/stdc++.h>
using namespace std;
int dp[200][200]; //dp(i,j)表示从i到j最小费用
int rent[200][200] ;
int getMinRent(int n){
    for(int i = 0 ; i < n-1 ;++i)
        dp[i][i+1] =rent[i][i+1];
    for (int l = 2 ; l < n ; ++l){
        for (int i = 0 ; i< n-1 ; ++i){
                dp[i][i+l] =rent[i][i+l];
            for(int k = 1 ; k < l ;++k){
                dp[i][i+l] = min(dp[i][i+l] ,dp[i][i+k] + dp[i+k][i+l]);
               // printf("i = %d , k = %d , j = %d ,dp =%d\n",i,k,i+l,dp[i][i+l]);
            }
        }
    }
    return dp[0][n-1];
}
//int getMinRenti(int n){
//
//    int dp[200] ;
//    for
//}
int main(){


    int n ;
    while (cin>>n){


        for (int i =0 ; i<n-1 ;++i){
            for(int j = i+1 ; j < n; ++j){
                cin>>rent[i][j] ;
            }
        }
        cout<<"minspent is "<<getMinRent(n);


    }
    return 0;
}

总结

以上是生活随笔为你收集整理的游艇租用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。