自动搬运

查看原文

来自洛谷，原作者为

	BIGBUG 一个蒟蒻

搬运于2025-08-24 21:24:10，当前版本为作者最后更新于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$