题目1086:最小花费
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:2082
解决:398
题目描述:
在某条线路上有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 2 3 1 2 3
1 2
2
2
样例输出:
2
#include <iostream>
using namespace std;
#define MAX 100000000000
typedef long long int64;
int64 l1,l2, l3, c1, c2, c3;
int64 arr[10000]; //存储i 到 i-1 的距离
int64 a,b;
int64 n;
int64 ans = MAX;
int64 cost[10000]; //存储最优花费
int64 getP(int64 l){
if(l == 0)
return 0;
else if(l <= l1)
return c1;
else if(l <= l2)
return c2;
else
return c3;
}
//从a到k的最优解,依赖于a到k-1的最优解。
void solve(int64 a,int64 b){
int64 len = b-a + 1;
for(int64 i=0; i<= len; i++)
cost[i] = MAX;
cost[0] = 0;
int64 tmp;
for(int i=a+1; i<=b; i++){
int64 k = i; //当前遍历到的位置
int64 cnt = 0;
int64 sum = arr[k];
//再往前遍历cnt个位置, 得到该位置的最优解
while(sum <= l3 && k-cnt > a){
cnt ++;
tmp = cost[k-a-cnt] + getP( sum );
if(cost[k-a] > tmp)
cost[k-a] = tmp;
sum += arr[i-cnt];
}
}
}
int main(){
while(cin >> l1 >> l2 >> l3 >> c1 >> c2 >> c3)
{
cin >> a >> b >> n;
if(a > b){
swap(a,b);
}
int64 pre = 0,cur;
for(int64 i=2; i<=n; i++)
{
cin >> cur;
arr[i] = cur - pre;
pre = cur;
}
if(a == b)
cout << 0 << endl;
else{
solve(a,b);
cout << cost[b - a] << endl;
}
}
return 0;
}
下面还有用Java写的递归版本。
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main{
static long L[] = new long [3];
static long P[] = new long [3];
static int station[] ;
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while(s.hasNextLong()){
for(int i=0; i<6; i++){
if(i>2)
P[i-3] = s.nextLong();
else
L[i] = s.nextLong();
}
int a = s.nextInt()-1;
int b = s.nextInt()-1;
int n = s.nextInt();
station = new int[n];
for(int i=1; i<n; i++)
station[i] = s.nextInt();
System.out.println(f(a,b));
}
}
private static long f(int a, int b) {
long len = station[b]-station[a];
if(b == a)
return 0;
else if(b-a == 1)
return getP(len);
else{
if(station[b]-station[b-1] < L[2])
return Math.min(f(a,b-1)+getP(station[b]-station[b-1]), f(a,b-2)+getP(station[b]-station[b-2]));
else
return f(a,b-1)+getP(station[b]-station[b-1]);
}
}
static long getP(long len){
if(len == 0)
return 0;
else if(len <= L[0])
return P[1];
else if(len <= L[1])
return P[1];
else
return P[2];
}
}
分享到:
相关推荐
针对石子合并问题,本文利用动态规划算法寻求石子合并时的最大,最小得分,选择相邻的两堆石子堆进行合并,其最终花费的代价与石子堆的排列顺序有关。根据其重叠子问题建立状态转移方程,利用程序进行求解。算例结果...
机器人最小能量,paul的机器人问题Paul有n个重物堆在一条线上。该重物由1连续编号到n, 最左边的物品编号为1,最右边的物品编号为n。已知每个物品的重量 ...你的任务是求解机器人收集所有重物可花费的最低能量值。
A 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决0/1背包问题的是(A ) A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照(C )的顺序。...
用递阶遗传算法优化多旅行商问题不需设计专门的遗传算子,操作简单,并且解码方法适于求解距离矩阵对称和距离矩阵非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化最小化完成时间的多旅行商...
多旅行商问题讨论的是如何安排N座城市,要求每个城市只允许被访问一次时,求解所有旅行商花费的费用和是最小(或最大)的问题。MTSP问题其实与单旅行商问题(Traveling Salesperson Problem,简称aSP)相似,但是由于...
输出占一行,对于给定的问题,如果找到了最小路程(花费),输出该最小花费,如果没有通路可以到达每个城市,则输出-1。 输入样例: Case 1: 4 -1 30 6 4 30 -1 5 10 6 5 -1 20 4 10 20 -1 Case 2: 5 -1 -1 -1 2...
而时间最小是本文完成任务后所追求的目标函数(在受时间、货物的重量和体积大小等因素作为限制条件),进行模型求解,使得模型的结果具有实际的意义和对实际的选择有帮助。所以本文在求解过程中,我们进行了符合实际...
在求解此问题过程中,需要优化的决策变量为每个客户的配送任务应该分配到哪一辆车上,以及每辆车完成客户配送任务的先后顺序,优化目标为最小化车辆总行驶距离和使用的车辆数。 故核心优化的目标为车辆总的固定成本...
29、 已知如下图,写出用动态规划求最短路径的递推关系式,并写出求从源点A0到终点A3 的最短路径过程。给出求解算法。 6 A1 A2 5 5 2 A0 A3 3 4 4 B1 B2 5 搜索与遍历问题 30、 已知有向图G=,E>,试设计一...
2)使用贪婪算法求解背包问题以及最小花费生成树问题。 二、方法原理 贪心算法就是做出一系列选择,使原问题达到最优解。在每一个决策点,都是做出当前看来的最优选择。 三、实验设备 PC机一台,C语言、PASCAL语言、...
基于最短路径分区聚类方法,以乘客、公交公司和轨道交通运营者三方的总花费最小为目标,通过改进染色体编码方法和遗传操作策略,成功解决了多对一模式下的接运公交网络设计问题.考察了公交线路长度和乘客需求对线路...
例1.2 使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。 单 位 销地 运 价 产地 B1 B2 B3 B4 B5 B6 B7 B8 产量 A1 6 2 6 7 4 2 5 9 60 A2 4 9 5 3 8 5 8 2 55 A3 5 2 1 9 7 4 3 3 51 A4 7...
该模型通过设置虚拟的基核,将正则化参数融入基核权重求解过程中;同时,通过将特征空间类内散度集成到多核优化目标函数中,在最小化训练误差的同时,使得同一模式的故障样本更加集中,有效提升了故障模式间的辨识力...
它提供了具有最小时间和二次形式后退水平配置的通用且通用的模型预测控制实现。 有关自定义构建说明(例如,使用其他第三方求解器进行编译),请参见此 。 有关更多常规信息和教程,请参考 。 生成状态: ROS ...
航空公司花费大量的人、...以最小化航班延误成本和取消成本为目标,结合飞机流平衡约束进行求解。计算结果表明,该模型可以较好地解决飞机路线恢复问题,为航空公司节省大量运营成本,所得方案符合航空公司实时控制的要求。
坐标点Matlab代码A-黎曼-次梯度-最小绝对距离问题求解器 该存储库包含 NeurIPS 2019 论文“”中提出的黎曼子梯度 (RSG) 求解器的实现(C++/Python/Matlab),用于使用以下公式解决最小绝对距离问题:其中X是形状为D ...
以设备空闲时间和工件平均流程时间加权均值最小化为目标函数对该问题进行了研究,采用遗传算法求解该NP-hard问题,染色体编码采用一种新的整数与实数相结合的方法,可实现对问题空间的全局随机寻优。算例研究显示,...
通常,大多数同类书籍都会花费大量的篇幅进行严格的理论推导和数学描述,而本书则更强调直观理解、实用工具和工程实践。 内容简介 本书全面论述了信号完整性问题。主要讲述了信号完整性和物理设计概论,带宽、电感...
通常,大多数同类书籍都会花费大量的篇幅进行严格的理论推导和数学描述,而本书则更强调直观理解、实用工具和工程实践。 内容简介 本书全面论述了信号完整性问题。主要讲述了信号完整性和物理设计概论,带宽、电感...
通常,大多数同类书籍都会花费大量的篇幅进行严格的理论推导和数学描述,而本书则更强调直观理解、 实用工具和工程实践。 内容简介 本书全面论述了信号完整性问题。主要讲述了信号完整性和物理设计概论,带宽、...