题解 | #最小花费#

线性逆序dp

f[i]表示从i站出发到达终点站的花费，那么从i站有3种选择：

1、买票1

2、买票2

3、买票3

假设买了其中一种票，到达了j站(j>i)，那么f[i]=票的价格+f[j]。 注意，ij站之间的距离小于等于l3，因为一张票可以走的最大距离就是l3.

按照上述思路，从后向前递推即可。

代码：

#include<iostream>
using namespace std;
typedef long long ll;
const int MAX=1e6+10;
ll f[MAX],a[MAX];
int main(){
    int l1,l2,l3,c1,c2,c3,A,B,n;
    while(~scanf("%d%d%d%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3,&A,&B,&n)){
        for(int i=2;i<=n;++i) scanf("%lld",&a[i]);
        if(A>B) swap(A,B);
        if(A==B){
            printf("%d\n",0);
            continue;
        }
        f[B]=0;
        for(int i=B-1;i>=A;--i){
            f[i]=1e18;
            int tt;
            //买票
            for(int j=i+1;j<=B&&a[j]-a[i]<=l3;++j){
                if(a[j]-a[i]<=l1) tt=c1;
                else if(a[j]-a[i]<=l2) tt=c2;
                else tt=c3;
                //更新花费
                f[i]=min(f[i],tt+f[j]);
            }
        }
        printf("%lld\n",f[A]);
    }
    return 0;
}