牛客网机试题-最小花费

题目描述

在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下: 距离s           票价 0<S<=L1         C1 L1<S<=L2        C2 L2<S<=L3        C3 输入保证0<L1<L2<L3<10^9,0<C1<C2<C3<10^9。 每两个站之间的距离不超过L3。 当乘客要移动的两个站的距离大于L3的时候，可以选择从中间一个站下车，然后买票再上车，所以乘客整个过程中至少会买两张票。 现在给你一个 L1，L2，L3，C1，C2,C3。然后是A B的值，其分别为乘客旅程的起始站和终点站。 然后输入N，N为该线路上的总的火车站数目，然后输入N-1个整数，分别代表从该线路上的第一个站，到第2个站，第3个站，……，第N个站的距离。 根据输入，输出乘客从A到B站的最小花费。

输入描述:

以如下格式输入数据：
L1  L2  L3  C1  C2  C3
A  B
N
a[2]
a[3]
……
a[N]

输出描述:

可能有多组测试数据，对于每一组数据，
根据输入，输出乘客从A到B站的最小花费。

示例1

输入

1 2 3 1 2 3
1 2
2
2

输出

2

首先判断贪心距离是不可以的，假如站之间很近每次都可以买最近的票，但万一最远的票特别贵呢

反之贪心票也是不对的，这里定义一个cost[i]代表到i站的最小花费，那么到n站的最小花费就看前面

哪个站（能买的到票的）到n站花费最小，更新就可以了

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int L[3],C[3];
int dis[110000];
ll cost[110000];
int main()
{
    int s,e,n,len;
    ll ans;
    while(scanf("%d%d%d",&L[0],&L[1],&L[2])!=EOF)
    {
        for(int i=0;i<3;i++) scanf("%d",&C[i]);
        scanf("%d%d",&s,&e);
        scanf("%d",&n);
        for(int i=2;i<=n;i++) scanf("%d",&dis[i]);
        ans=0;
        cost[s]=0;
        for(int i=s+1;i<=e;i++)
        {
            ll temp=1e18;
            for(int j=i-1;j>=s;j--)
            {
                int now=cost[j];
                int len=dis[i]-dis[j];
                if(len<=L[0]) now+=C[0];
                else if(len<=L[1]) now+=C[1];
                else if(len<=L[2]) now+=C[2];
                else break;
                if(now<temp) temp=now;
            }
            cost[i]=temp;
        }
        printf("%lld\n",cost[e]);
    }
    return 0;
}