题解 | 最小花费

#include<bits/stdc++.h>
#define int long long
#define _for(i, a, b) for(int i = a;i < b;++i)
#define _rep(i, a, b) for(int i = a;i <= b;++i)
int readll(){int x; scanf("%lld", &x); return x;}
using namespace std; 
#define INF 0x3f3f3f3f
const int maxn = 100 + 5;

int dp[maxn][maxn], martix[maxn][maxn];//dp[i][j]: i->j minimum cost, martix[i][j]: i->j distance 
int L1, L2, L3, C1, C2, C3, A, B, N;

int judge(int x){
	if(x > L2)	return C3;
	if(x > L1)	return C2;
	return C1;
}

signed main(){
	cin>>L1>>L2>>L3>>C1>>C2>>C3>>A>>B>>N;
	memset(dp, INF, sizeof(dp));
	_rep(i, 2, N)	martix[1][i] = martix[i][1] = readll();
	_for(i, 1, N){
		dp[i][i] = 0;
		int j = i + 1;
		dp[i][j] = judge(abs(martix[1][j] - martix[1][i]));
	}
	dp[N][N] = 0;
	_for(dis, 2, N){//对角线差值 
		int len = N - dis;//当前对角线遍历的长度 
		_rep(i, 1, len){
			int j = i + dis;
			int temp = abs(martix[1][j] - martix[1][i]);
			if(temp <= L3)	dp[i][j] = min(judge(temp), dp[i][j]);
			_for(k, i + 1, j)	dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
		}
	}
	/*	
	cout<<endl;
	_rep(j, 1, N){
		_rep(i, j, N)	cout<<dp[i][j]<<' ';
		cout<<endl;
	} 
	*/
	cout<<dp[A][B]<<endl;
	return 0;
}

区间dp