最小花费

/*动态规划法，参考了263保洁小妹大佬的代码*/
#include "stdio.h"
#include "limits.h"
//其中宏定义的括号要加上，因为如果在Price(x)参加运算的时候，
//如果没有括号会因为优先级的问题，使得表达式的值最终等于冒号表达式的？或：后的值
#define Price(x) ((x)>l1?(x)>l2?c3:c2:c1) 
#define Min(x,y) ((x)<(y)?x:y)
int a[1000],cost[1000];

int main(){
    int l1,l2,l3,c1,c2,c3,A,B,n,i,j;
    while(scanf("%d%d%d%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3,&A,&B,&n) != EOF){
        for(i = 2; i <= n; i++){
            scanf("%d",&a[i]);
        }
        cost[A] = 0;
        for(i = A+1; i <= B; i++){
            cost[i] = cost[i-1] + Price(a[i]-a[i-1]);
        }//初始化状态，认为每一站都买了票，后面再对每一站都买票的情况进行优化
        for(i = A+1; i <= B; i++){
            //考虑从A站到一层循环当前i站中间的所有站
            //更新方法就是从i站前的每一站开始考虑，这一站到i站的花费是否可以减少
            //如果i,j两地的距离小于l3，就要考虑另一种买票选择
            //感觉这题和最小邮票数还挺像的。
            for(j = i-1; (a[i] - a[j] <= l3) && j >= A; j--){
                cost[i] = Min(cost[i],cost[j]+Price(a[i] - a[j]));
            }
        }
        printf("%d\n",cost[B]);
    }
    return 0;
} 

package tsinghua;

import java.util.Scanner;

/*
 *	QQ:	825580813(一起来敲代码)
 */
public class MinCost {
	
	static int[] L = new int[3];
	static int[] C = new int[3];
	static int A, B, N;
	static int[] distance;		//distance[i] 表示 第1站 到 第i + 1站 的距离
	static int[] dp;			//dp[i] 表示 第一站 到 第i + 1站 的最小花费

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			for (int i = 0; i < L.length; ++i) {
				L[i] = sc.nextInt();
			}
			for (int i = 0; i < C.length; ++i) {
				C[i] = sc.nextInt();
			}
			A = sc.nextInt();
			B = sc.nextInt();
			N = sc.nextInt();
			distance = new int[N];
			for (int i = 1; i < distance.length; ++i) {
				distance[i] = sc.nextInt();
			}
			int res = getMinCost();
			System.out.println(res);
		}
		sc.close();
	}

	//用动态规划的方法求出dp的值
	private static int getMinCost() {
		dp = new int[distance.length];
		dp[1] = getPrice(distance[1]);	//第2站的最小花费就是 第1站 到 第2站 的花费.
		for (int i = 2; i < distance.length; ++i) {
			int interval = distance[i] - distance[i - 1];	//第i站 与 前一站 的间隔
			//第i站 的初始赋值,就是前一站的花费 + 前一站 到第 i 站的花费
			dp[i] = dp[i - 1] + getPrice(interval);			
			for (int j = i - 2; j >= 0; --j) {		//试探是否可以通过前几站 直接坐到 第i站(中途不下车)
				interval = distance[i] - distance[j];//第j站 到 第i站的间隔
				if (interval > L[2]) {		//如果间隔大于L3的话,j前面的站就不能直达第i站了,跳出
					break;
				}
				dp[i] = Math.min(dp[i], dp[j] + getPrice(interval));
			}
		}
		return dp[B - 1] - dp[A - 1];
	}

	//根据一段距离计算出花费
	private static int getPrice(int dis) {
		for (int i = 0; i < L.length; ++i) {
			if (dis <= L[i]) {
				return C[i];
			}
		}
		return 0;
	}

}

import java.util.Scanner;

public class LeastCost {
    public static void main(String[] a){
        Scanner scanner =new Scanner(System.in);
        while (scanner.hasNext()){
            int L1 =scanner.nextInt();
            int L2 =scanner.nextInt();
            int L3 =scanner.nextInt();
            int C1 =scanner.nextInt();
            int C2 =scanner.nextInt();
            int C3 =scanner.nextInt();
            int A  =scanner.nextInt();
            int B  =scanner.nextInt();
            int N  =scanner.nextInt();
            int[] Array = new int[N+1];
            for(int i=2;i<=N;i++)
                Array[i]=scanner.nextInt();

            int[] cost =new int[N+1];
            for(int i=A+1;i<=B;i++)
                cost[i]=9999999;
            for (int i=A;i<=B;i++){ //一轮循环即可
                 int index1 =(i+NumOfStation(L1,Array,i)>=B)?B:(i+NumOfStation(L1,Array,i));
                 int index2 =(i+NumOfStation(L2,Array,i)>=B)?B:(i+NumOfStation(L2,Array,i));
                 int index3 =(i+NumOfStation(L3,Array,i)>=B)?B:(i+NumOfStation(L3,Array,i));

                 cost[index1]=Math.min(cost[index1],cost[i]+C1);
                 cost[index2]=Math.min(cost[index2],cost[i]+C2);
                 cost[index3]=Math.min(cost[index3],cost[i]+C3);
            }

            System.out.println(cost[B]);
        }
    }
    public static int NumOfStation(int distance,int[] array,int startpos){ //走L距离能过多少站
        int countDis=0;
        int countStations=0;
        for (int i=startpos;i<array.length>distance)
                break;
        }
        return countStations-1;
    }
}

</array.length>

1.  //看成最短路径问题用Dijkstra解决
    #include <stdio.h>
    #include <limits.h>
    #include <vector>
    using namespace std;
    struct E{
        int next;
        int c;
    };
    vector<E> edge[100];
    bool mark[100];
    int Dis[100],a[100];
    int main()
    {
        //freopen("in.txt","r",stdin);
        int L1,L2,L3,C1,C2,C3,A,B,n;
        while(scanf("%d%d%d%d%d%d",&L1,&L2,&L3,&C1,&C2,&C3)!=EOF)
        {
            scanf("%d%d%d",&A,&B,&n);
            for(int i=2;i<=n;i++) scanf("%d",&a[i]);
            //Build Graph
            for(int i=1;i<=n;i++) edge[i].clear();
            for(int i=1;i<=n;i++){
                for(int j=i+1;a[j]-a[i]<=L3 && j<=n;j++){
                    E tmp;
                    if(a[j]-a[i]<=L1) tmp.c=C1;
                    else if(a[j]-a[i]<=L2 && a[j]-a[i]>L1) tmp.c=C2;
                    else tmp.c=C3;
                    tmp.next=j;
                    edge[i].push_back(tmp);
                }
            }
            //Dijkstra Init
            for(int i=1;i<=n;i++){
                Dis[i]=-1; //所有距离不可达
                mark[i]=false; //所有节点不属于集合K
            }
            Dis[A]=0; //第一近点为A，长度0
            mark[A]=true; //将A加入集合K
            int newP=A; //新加入点为A
            //Dijkstra Main
            for(int i=A;i<n;i++){ //每次循环确定一个最近点
                for(int j=0;j<edge[newP].size();j++){
                    int t=edge[newP][j].next;
                    int c=edge[newP][j].c;
                    if(mark[t]==true) continue;
                    if(Dis[t]==-1 || Dis[t]>Dis[newP]+c) Dis[t]=Dis[newP]+c;
                }
                int min=INT_MAX;
                for(int j=A+1;j<=n;j++){
                    if(mark[j]==true) continue;
                    if(Dis[j]<=-1) continue;
                    if(Dis[j]<min){
                        min=Dis[j];
                        newP=j;
                    }
                mark[newP]=true;
                }
            }
            printf("%d\n",Dis[B]);
        }
        return 0;
    }
    

   
   

def fareNum(distance):
    if distance <= length[0]:
        return costs[0]
    elif distance <= length[1]:
        return costs[1]
    else:
        return costs[2]
try:
    while True:
        tempInput = list(map(int,input().split()))
        length = tempInput[:3]
        costs = tempInput[3:]
        a,b = list(map(int,input().split()))
        if a > b:
            a,b = b,a
        n = int(input())
        distances = [0,0]                    #distances[i]表示第一个车站到第i个车站的路程
        for i in range(n-1):
            distances.append(int(input()))
        spend = [float('inf')] * (n+1)       #spend[i]表示车站a到车站i的最小花费
        spend[a] = 0
        for i in range(a+1,b+1):
            temp = i - 1                     #从前一个开始查找最少花费
            while temp >= a and (distances[i]-distances[temp]) <= length[2]:
                spend[i] = min(spend[i],spend[temp]+fareNum(distances[i]-distances[temp]))
                temp -= 1
        print(spend[b])
except Exception:
    pass

思想没错，就是超时了，估计C++能过

package com.speical.first;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/** 
* 最小花费
* 
* bfs 你们仅仅学习一下思想吧
* java竟然超时，c++没试
* @author special
* @date 2017年12月23日 下午2:36:19
*/
public class Pro22 {
    private static int[] dis = new int[3];
    private static int[] price = new int[3];

    static class Node{
        int index;
        int sum;
        public Node(int index, int sum){
            this.index = index;
            this.sum = sum;
        }
    }
    public static int bfs(int start, int end, int[] tDis){
        int min = Integer.MAX_VALUE;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(start, 0));
        while(!queue.isEmpty()){
            Node node = queue.remove();
            if(node.index == end){
                min = Math.min(min,node.sum);
                continue;
            }
            for(int i = node.index + 1; i <= end; i++){
                int d = tDis[i] - tDis[node.index];
                if(d > dis[2]) break;
                if(d >= 0 && d <= dis[0]){
                    queue.offer(new Node(i, node.sum + price[0]));
                }else if(d > dis[0] && d <= dis[1]){
                    queue.offer(new Node(i, node.sum + price[1]));
                }else{
                    queue.offer(new Node(i, node.sum + price[2]));
                }
            }
        }
        return min;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            for(int i = 0; i < 3; i++){
                dis[i] = input.nextInt();
            }
            for(int i = 0; i < 3; i++){
                price[i] = input.nextInt();
            }
            int start = input.nextInt();
            int end = input.nextInt();
            int N = input.nextInt();
            int[] tDis = new int[N + 1];
            for(int i = 2; i <= N; i++){
                tDis[i] = input.nextInt();
            }
            System.out.println(bfs(start,end,tDis));
        }
    }

}

#include<iostream>
using namespace std;
int main() {
	int N, A, B;
	long long Distance[10000];
	long long Dp[10000];
	long long L1, L2, L3, C1, C2, C3;
	long long temp_length;
	long long temp_cost;
	while (cin >> L1 >> L2 >> L3 >> C1 >> C2 >> C3) {
		cin >> A >> B >> N;
		Distance[1] = 0;
		for (int i = 2; i <= N; ++i)
			cin >> Distance[i];
		if (A == B) {
			cout << '0' << endl;
			continue;
		}
		if (A > B) {
			int temp = A;
			A = B;
			B = temp;
		}

		for (int i = A; i <= B; ++i)
			Dp[i] = -1;
		Dp[A] = 0;
		for (int i = A; i <= B; ++i) {    
			for (int j = i + 1; j <= B; ++j) {
				temp_length = Distance[j] - Distance[i];
				if (temp_length > L3)							break;
				else if (L2 < temp_length && temp_length <= L3)	temp_cost = C3;
				else if (L1 < temp_length && temp_length <= L2)	temp_cost = C2;
				else											temp_cost = C1;
				if (Dp[j] == -1 || Dp[i] + temp_cost < Dp[j])	Dp[j] = Dp[i] + temp_cost;
			}
		}
		cout << Dp[B] << endl;
	}
	return 0;
}

#include <stdio.h>
#include <limits.h>
#define N 500

int dist[N], cost[N];//第i个站的总里程、最少花费
int l1, l2, l3, c1, c2, c3;

int Price(int L)//L距离的票多少钱
{
    if(L<=l1) return c1;
    else if(L<=l2) return c2;
    else return c3;
}

int main()
{
    int n, from, to;
    while(scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3)!=EOF)
    {
        dist[1]=0;//始发站里程为0
        scanf("%d %d", &from, &to);
        scanf("%d", &n);
        for(int i=2; i<=n; i++) scanf("%d", &dist[i]);
        cost[from]=0;//出发之前，没花一毛钱
        for(int i=from+1; i<=to; i++)//前进！！！
        {
            cost[i]=INT_MAX;//先假设到i站需要花无数的钱
            for(int j=from; j<i; j++)//到i站的票可能是从j站买的
            {
                int L=dist[i]-dist[j];//j站到i站的距离
                if(L<=l3&&cost[j]+Price(L)<cost[i])
                {//如果从j站买票能比以往的方案更省钱，那就从j买票
                    cost[i]=cost[j]+Price(L);
                }
            }
        }
        printf("%d\n", cost[to]);
    }
    return 0;
}

参考了其他人的方法，给出了自己实现的代码和详细注释，希望对你有用

#include<bits/stdc++.h>
using namespace std;
int L1,L2,L3,C1,C2,C3,N;
int A,B;
int price(int dis){
	if(dis<=L1) return C1;
	if(dis<=L2) return C2;
	if(dis<=L3) return C3;
        //其余情况不可能出现
} 
//1.本算法利用动态规划 
//2.亦可以看成一张图，每个站点都与其他站点相连，且刚开始只知道相连站点间的花费 
//然后利用图中 Dijkstra 求当前节点到每个节点的最小花费 
int main(){
	while(cin>>L1>>L2>>L3>>C1>>C2>>C3>>A>>B>>N){
		int dis[N+1];
		int cost[N+1];//cost[i] 代表从 A -> i 的最小花费 
		for(int i=2;i<=N;i++){
			cin>>dis[i];
		}
		//初始化
		cost[A]=0;  //A -> A花费为 0 
		for(int i=A+1;i<=B;i++){
			cost[i]=INT_MAX;  //A -> 其余各站的最小花费 还不知道 
		} 
		//每次前进一站,并计算出 A -> 该站 的最小花费 
		for(int i=A+1;i<=B;i++){
			//到达 i 站 前的最后一次中转站 有 i-A 个可能 
			for(int j=A;j<i;j++){
				if(dis[i]-dis[j]<=L3){//如果从 j 站 中转一次可以到 i 站 
					cost[i]=min(cost[i],cost[j]+price(dis[i]-dis[j]));
				}	
			}
		} 
		//输出结果
		cout<<cost[B]<<endl; 
	}
	return 0;
} 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define price(x) ((x) <= l2 ? ((x) <= l1 ? c1 : c2) : c3)
#define min(x, y) ((x) <= (y) ? (x) : (y))

int main() {
    int l1, l2, l3, c1, c2, c3, a, b, n;
    while (scanf("%d %d %d %d %d %d", &l1, &l2, &l3, &c1, &c2, &c3) != EOF) {
        scanf("%d %d", &a, &b);
        scanf("%d", &n);
        
        // 确保 a <= b
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }

        int* arr = (int*)malloc(sizeof(int) * (n + 1));
        arr[1] = 0;  // 起点距离为 0
        for (int i = 2; i <= n; i++) {
            scanf("%d", &arr[i]);
        }

        int size = b - a + 1;
        int* distance = (int*)malloc(sizeof(int) * size);
        int* dp = (int*)malloc(sizeof(int) * size);

        // 初始化 distance 和 dp
        for (int i = 0; i < size; i++) {
            distance[i] = arr[i + a] - arr[a];
            dp[i] = INT_MAX;  // 初始化为无穷大
        }
        dp[0] = 0;  // 起点花费为 0

        // 动态规划计算最小花费
        for (int i = 1; i < size; i++) {
            for (int j = i - 1; j >= 0; j--) {
                int dist = distance[i] - distance[j];
                if (dist > l3) break;  // 超过 l3，直接跳过
                dp[i] = min(dp[i], dp[j] + price(dist));
            }
        }

        printf("%d\n", dp[size - 1]);

        // 释放内存
        free(arr);
        free(distance);
        free(dp);
    }
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int l1, l2, l3, c1, c2, c3;
int a, b, n;
int w[N];
int dp[N];

int value(int u, int v) {
	int dis = w[v] - w[u];
	if (dis <= l1) return c1;
	else if (dis <= l2) return c2;
	else return c3;
}

int main() {
    while (cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3) {
		cin >> a >> b >> n;
		w[1] = 0;
		for (int i = 2; i <= n; i++) {
			cin >> w[i];
		}
		dp[1] = 0;
		dp[2] = value(1, 2);
		for (int i = 3; i <= b; i++) {
			dp[i] = 1e9;
			for (int j = 1; j < i; j++) {
				int dis = w[i] - w[i - j];
				if (dis > l3) break;
				dp[i] = min(dp[i], dp[i - j] + value(i - j, i));
			}
		}
		cout << dp[b] - dp[a] << endl;
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] a;
    static int L1;
    static int L2;
    static int L3;
    static int C1;
    static int C2;
    static int C3;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            String[] s1 = s.split(" ");
            L1 = Integer.parseInt(s1[0]);
            L2 = Integer.parseInt(s1[1]);
            L3 = Integer.parseInt(s1[2]);
            C1 = Integer.parseInt(s1[3]);
            C2 = Integer.parseInt(s1[4]);
            C3 = Integer.parseInt(s1[5]);
            String[] s2 = br.readLine().split(" ");
            int A = Integer.parseInt(s2[0]);
            int B = Integer.parseInt(s2[1]);
            int N = Integer.parseInt(br.readLine());
            a = new int[N + 1];
            for (int i = 2; i <= N; i++) {
                a[i] = Integer.parseInt(br.readLine());
                //a[i]表示第1站到第i站的距离 1～2为a[2]  1~3为a[3] ......
            }
            //数据录入完毕

            int[] dp = new int[N + 1 + A];
            //dp[i]表示A到第i站的最短花费
            dp[A] = 0;//A~A
            for (int i = A + 1; i <= B; i++) {
                dp[i] = Integer.MAX_VALUE;
                for (int j = A; j <= i; j++) {
                    int d = a[i] - a[j];
                    if (d <= L3)
                        dp[i] = Math.min(dp[i], dp[j] + cost(d));
                    else {
//                        continue;
                        int cost = 0;
                        for (int k = j; k < i; k++) {
                            cost += cost(a[k + 1] - a[k]);
                        }
                        dp[i] = Math.min(dp[i], dp[j] + cost);
                    }
                    //两站间距离大于L3时就跳过，不用计算
                    //因为要下车再买票，一直到剩下的几站距离小于等于L3为止（一定会有两站间距离小于等于L3的，因为每两个站之间的距离不超过L3）
                    //假设要算2～9站的最少票价，乘客原本坐到了5站，发现剩余距离远大于L3，那乘客就得往后坐一站，再次做比较，发现还大于L3，继续坐一站。。。。
                    //直到剩余的距离小于L3，这里假设7～9的距离<L3,这种情况下我买的票情况：2～5是最少花费（dp数组)+5～6的票价+6～7的票价+7～9的票价
                    //这种情况下一定不是最少票价，后期一定会被2~7的最少花费（dp数组)+7～9的票价所更新
                }
            }
            System.out.println(dp[B]);
        }

    }

    private static int cost(int distence) {
        int price = 0;
        if (distence <= L1) price = C1;
        else if (distence <= L2) price = C2;
        else price = C3;
        return price;
    }

}

#include<iostream>
#include<limits.h>

using namespace std;

int l1,l2,l3,c1,c2,c3;

int price(int d){
    if(d<=l1) return c1;
    else if(d<=l2) return c2;
    else  return c3;
}

int main(){
    while(cin>>l1>>l2>>l3>>c1>>c2>>c3){
        int a,b;
        cin>>a>>b;
        
        int n;
        cin>>n;
        int L[n+1];
        L[1] = 0;
        for(int i=2;i<=n;i++){
            cin>>L[i];
        }
        
        int dp[n+1];
        dp[a]=0;
        
        for(int i=a+1;i<=b;i++){
            int min = INT_MAX;
            for(int j=a; j<i;j++){
                int d = L[i]-L[j];
                if(d<=l3) { 
                    dp[i]= dp[j] + price(d);
                    if(dp[i]<min) min = dp[i];
                }
            }
            dp[i] = min;
        }
        
        cout<<dp[b]<<endl;
    }
    return 0;
}

#include <stdio.h>
#include <vector>
using namespace std;
int l1,l2,l3,c1,c2,c3;
bool mark[1000];
int dis[1000];
struct Edge
{
    int to;
    int cost;
};
vector graph[1000];
int help[1000];
void init(int a,int b)
{
    for(int i=a;i<=b;i++) 
    {
        mark[i] = false;
        graph[i].clear();
        dis[i] = -1;
    }
    for(int i=a;i<=b;i++)
    {
        for(int j=i+1;j<=b;j++)
        {
            int tmp = help[j]-help[i];
            Edge e;
            e.to = j;
            if(tmp<=l1) e.cost = c1;
            else if(tmp<=l2) e.cost = c2;
            else if(tmp<=l3) e.cost = c3;
            else continue;
            graph[i].push_back(e);
        }
    }
}
int main()
{
    int a,b,n;
    while(scanf("%d%d%d%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3,&a,&b,&n)!=EOF)
    {
        for(int i=2;i<=n;i++) scanf("%d",&help[i]);
        init(a,b);
        dis[a] = 0;
        mark[a] = true;
        int newN = a;
        int cnt = b - a;
        for(int i=1;i<=cnt;i++)
        {
            for(int j=0;j<graph[newN].size();j++)
            {
                int tmp = graph[newN][j].to;
                int c = graph[newN][j].cost;
                if(mark[tmp] == true) continue;
                if(dis[tmp] == -1 || dis[tmp]>dis[newN]+c) 
                    dis[tmp] = dis[newN]+c;
            }
            int min=123123123;
            for(int j=a;j<=b;j++)
            {
                if(mark[j] == true) continue;
                if(dis[j] == -1) continue;
                if(min>dis[j]) 
                {
                    min = dis[j];
                    newN = j;
                }
            }
            mark[newN] = true;
        }
        printf("%d\n",dis[b]);
    }
}