题解 P1359 【租用游艇】

BIGBUG · 2019-07-30 14:11:26 · 题解

这道题是一道dp题，。

首先，我们要先存图。

看看样例吧：

3
5 15
7

显然，5和15是中转站1到2和3的价钱，而7是2到3的价钱。我们可以用a数组来存，a[i][j]表示i到j的价钱。（左边表示出发站，右边表示到达站）

我们可以用dp数组来记录这个中转站到n号中转站的最小价钱，dp[i]表示中转站i到中转站n的最小价钱。

我们要用i把n上流的中转站从大到小跑一遍。我们先记录中转站2到中转站3的最小价钱，我们要用j跑一遍中转站2下流的所有中转站，记录a[i][j]+dp[j]的最小价钱,记录到dp[i]里面。

附上代码：

#include<iostream>
#include<cmath>
using namespace std;
int a[201][201],i,j,n,dp[201];
int main(){
    cin>>n;
    for(i=1;i<n;i++){
        for(j=i+1;j<=n;j++)
            cin>>a[i][j];
        dp[i]=1e9;//初始化数组dp，使它
    }
    for(i=n-1;i>=1;i--)//跑n上流的中转站
        for(j=i+1;j<=n;j++)//跑i下流的所有中转站
            dp[i]=min(dp[i],a[i][j]+dp[j]);//记录
    cout<<dp[1];
    return 0;
}

PS：蒟蒻的题解，大佬勿喷！qwq