蒟蒻的思路 - 题解

讨论

题解

火车票

蒟蒻的思路

题目思路：

其实呢……

个人觉得这道题记忆化更香

怎么说呢？

记忆化非常好想到，应为只要把dp[i]作为到达第i站的最小花费即可

剩下的就模拟暴力即可

——————————————————————————

下面是AC代码：


#include<bits/stdc++.h>

#define int long long

const long long maxn = 1e2+10;

using namespace std; 

int d1,d2,d3,c1,c2,c3;

int n,s,e;

int sum[maxn],x;

int dp[maxn];

void DFS(int deep,int cnt){

	int i=1,f;

	if(dp[deep] <= cnt)return ;//记忆化 

	dp[deep] = cnt;

	if(deep == e)return ;//到达终点就完事 

	if(e>deep) f=1;//判断行走方向，简化代码 

	else f=-1;

	//接下来的都是模拟，自行细品 

	while(abs(sum[deep+i*f]-sum[deep]) <= d1){

		if(deep+i*f>n || deep+i*f <1)break;

		DFS(deep+i*f,cnt+c1);

		i++;

	}

	while(abs(sum[deep+i*f]-sum[deep]) <= d2){

		if(deep+i*f>n || deep+i*f <1)break;
 
		DFS(deep+i*f,cnt+c2);

		i++;

	}

	while(abs(sum[deep+i*f]-sum[deep]) <= d3){

		if(deep+i*f>n || deep+i*f <1)break;

		DFS(deep+i*f,cnt+c3);

		i++;

	}
	
}

signed main()

{

	cin>>d1>>d2>>d3>>c1>>c2>>c3;

	cin>>n;

	cin>>s>>e;

	dp[1]=INT_MAX;
 
	for(int i=2;i<=n;i++){

		dp[i]=INT_MAX;

		cin>>sum[i];

	}

	DFS(s,0);

	cout<<dp[e];//输出终点的最小花费 

	return 0;

}