题目描述
在某条线路上有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
注意:
有的测试数据比较大,简单的dp,注意用long long类型就好了,用scanf和printf,占位符用%lld,vc6.0里面没有long long,只有__int64,输入输出占位符用%I64d,注意提交的时候改过来就好了,题意没说l1,l2,l3,c1,c2,c3的数据类型,根据提交的代码分析,都是整数。
在某条线路上有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> #include <stdio.h> #define MAX_N 1001 #define INF 9999999999 using namespace std; int n; long long dp[MAX_N][MAX_N]; long long l1,l2,l3,c1,c2,c3; int a,b; long long dist[MAX_N]; long long cost(int _a,int _b) { long long d=dist[_b]-dist[_a]; if(0==d) return 0; if(0<d && d<=l1) return c1; if(l1<d && d<=l2) return c2; if(l2<d && d<=l3) return c3; else return INF; } long long dpit(int _a,int _b) { long long min; if(dp[_a][_b]) return dp[_a][_b]; min=cost(_a,_b); for(int i=_a+1;i<_b;i++) { if(min>dpit(_a,i)+cost(i,_b)) min=dpit(_a,i)+cost(i,_b); } dp[_a][_b]=min; return min; } int main() { int i,j; while(scanf("%lld%lld%lld%lld%lld%lld",&l1,&l2,&l3,&c1,&c2,&c3)==6) { cin>>a>>b; cin>>n; dist[1]=0; for(i=2;i<=n;i++) { scanf("%lld",&dist[i]); } for(i=1;i<=n;i++) for(j=1;j<=n;j++) dp[i][j]=0; printf("%lld\n",dpit(a,b)); } return 0; }
注意:
有的测试数据比较大,简单的dp,注意用long long类型就好了,用scanf和printf,占位符用%lld,vc6.0里面没有long long,只有__int64,输入输出占位符用%I64d,注意提交的时候改过来就好了,题意没说l1,l2,l3,c1,c2,c3的数据类型,根据提交的代码分析,都是整数。
发表评论
-
2011清华考研机试题2
2011-08-09 14:56 909http://ac.jobdu.com/problem.php ... -
2011清华考研机试题1
2011-08-09 14:40 642题目描述 http://ac.jobdu.com/proble ... -
poj3259 spfa解法
2011-08-08 19:59 1356同上题,不过改的spfa算法,注意每个节点进入队列的次数至多为 ... -
poj3259 bellman水题
2011-08-08 17:04 969poj3259http://poj.org/problem?i ... -
acm题目常用的预处理
2011-08-08 15:26 1163#include<iostream> #in ... -
poj1860
2011-08-08 14:06 705poj1860http://poj.org/problem?i ... -
water~9
2011-08-06 18:01 418poj2109http://poj.org/problem?i ... -
water~8
2011-08-06 17:22 574poj2027http://poj.org/problem?i ... -
water~7
2011-08-06 17:15 568poj1328http://poj.org/problem?i ... -
water~6
2011-08-06 14:27 707poj1088http://poj.org/problem?i ... -
water~5
2011-08-06 14:24 581poj1003http://poj.org/problem?i ... -
water~4
2011-08-06 14:09 637poj1004http://poj.org/problem?i ... -
water~3
2011-08-06 13:59 522poj2159http://poj.org/problem?i ... -
water~2
2011-08-06 12:10 533poj3299http://poj.org/problem?i ... -
water~1
2011-08-06 10:35 639poj1503http://poj.org/problem?i ... -
POJ3280 简单DP
2011-08-05 14:48 893poj3280:http://poj.org/problem? ... -
POJ3253
2011-08-04 13:36 780poj3253:http://poj.org/problem? ...
相关推荐
哈工大考研复试C语言机考试题及代码,希望能对考研的同学有所帮助。
(精华版)国家开放大学电大《政府经济学》机考3套真题题库及答案6.pdf
华为OD机考100题
包含北京大学机考数据结构题目,可以为即将参加机考的同学提供个方向
浙江大学研究生考试复试题。多是照片形式。欢迎大家下载。
关于武汉大学复试机考的一点整理
2018电大机械制图机考网考题库
北邮计算机研究生复试历年上机测试模拟试题及真题.pdf
包括清华大学06年-18年的上机考试试题真题,对于复试上机考试非常有帮助
华为机考试题+答案参照.pdf
南开机考100题.doc 南开机考100题.doc 南开机考100题.doc 南开机考100题.doc 南开机考100题.doc
三、能学到什么:通过本文档可以学到华为OD机考的题型以及考察的重点, 四、阅读建议:先自己做一遍,然后再去翻看答案。只有这样才能更好的对自身的知识掌握情况有一个清楚的认识。 一、内容概要:本文档从华为OD...
华为校招硬件技术工程师机考试卷试题包括答案.docx
Java机考200题.pdf
2020国开《建筑材料(A)》期末机考真题库9.pdf
东北大学计算机硬件基础机考编程题题库.pdf
北邮复试上机题目
专升本 机考模拟题
国家开放大学电大《建筑制图基础》机考网考题库及答案.pdf
华为机考-软件测试试题