九度oj 题目1086：最小花费
2024-09-08 09:52:41
- 题目描述：
-
在某条线路上有N个火车站，有三种距离的路程，L1，L2，L3,对应的价格为C1,C2,C3.其对应关系如下:距离s 票价0<S<=L1 C1L1<S<=L2 C2L2<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 C3A BNa[2]a[3]……a[N]
- 输出：
-
可能有多组测试数据，对于每一组数据，根据输入，输出乘客从A到B站的最小花费。
- 样例输入：
-
1 2 3 1 2 3
1 2
2
2
- 样例输出：
-
2 这道题真是一个惨痛的回忆。
开始的思路是普通的动态规划思路，即经典的分割问题，最后通过的代码如下#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 300
#define inf 10000000009 long long minCost[MAX][MAX];
long long dis[MAX][MAX];
long long dis0[MAX]; int main(int argc, char const *argv[])
{
long long L1, L2, L3, C1, C2, C3;
//freopen("input.txt","r",stdin);
while(scanf("%lld %lld %lld %lld %lld %lld",&L1, &L2, &L3, &C1, &C2, &C3) != EOF)
{
int A, B;
int N;
scanf("%d %d",&A,&B);
scanf("%d",&N);
dis0[] = ;
for(int i = ; i <= N; i++) {
scanf("%lld",&dis0[i]);
}
for(int l = ; l <= N - ; l++) {
//length from 1 to N - 1
for(int i = ; i <= N - l; i++) {
//start from i to N - l
int j = i + l;
//end is i + l
dis[i][j] = dis0[j] - dis0[i];
if(dis[i][j] <= L1) {
minCost[i][j] = C1;
}
else if(dis[i][j] <= L2) {
minCost[i][j] = C2;
}
else if(dis[i][j] <= L3) {
minCost[i][j] = C3;
}
else {
minCost[i][j] = inf;
} for(int k = i + ; k <= j-; k++) {
long long int q = minCost[i][k] + minCost[k][j];
if(q < minCost[i][j]) {
minCost[i][j] = q;
}
}
}
}
if(A < B) {
printf("%lld\n",minCost[A][B]);
}
else if(A > B){
printf("%lld\n",minCost[B][A]);
}
else {
printf("%d\n",);
} }
return ;
}但代码一开始提交了n次都没有通过，经过很长时间的排查，终于发现了原因。一开始我设的inf是
1000000009,WA改成了
10000000009后就AC了。
之后我发现没必要去算出每两个点之间的最小花费，只需要计算出从A到B之间的最小花费即可，dis数组也不需要
代码如下：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 300
#define inf 10000000009 long long minCost[MAX][MAX];
long long dis0[MAX]; int main(int argc, char const *argv[])
{
long long L1, L2, L3, C1, C2, C3;
//freopen("input.txt","r",stdin);
while(scanf("%lld %lld %lld %lld %lld %lld",&L1, &L2, &L3, &C1, &C2, &C3) != EOF)
{
int A, B;
int N;
scanf("%d %d",&A,&B);
scanf("%d",&N); for(int i = ; i <= N; i++) {
scanf("%lld",&dis0[i]);
}
if(A > B) {
int temp = A;
A = B;
B = temp;
}
long long n = B - A;
dis0[] = ;
minCost[A][A] = ;
for(int l = ; l <= n; l++) {
//length from 1 to N - 1
for(int i = A; i <= A + n - l; i++) {
//start from i to N - l
int j = i + l;
//end is i + l
long long temp = dis0[j] - dis0[i];
if(temp <= L1) {
minCost[i][j] = C1;
}
else if(temp <= L2) {
minCost[i][j] = C2;
}
else if(temp <= L3) {
minCost[i][j] = C3;
}
else {
minCost[i][j] = inf;
} for(int k = i + ; k <= j-; k++) {
long long int q = minCost[i][k] + minCost[k][j];
if(q < minCost[i][j]) {
minCost[i][j] = q;
}
}
}
}
printf("%lld\n",minCost[A][B]); }
return ;
}但是我们研究一下会发现，如果两地的距离小于L3,则它们之间的最小花费必然在C1,C2,C3之间，所以若将minCost改为一维数组，将i作为中间点，j作为终点,当i到j的距离小于L3时，minCost[j] = min (minCost[j], minCost[i] + Ci); 所以遍历i时，选取与其距离小于L3的j，即可。代码如下:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#define MAX 150
#define inf 10000000009 long long minCost[MAX];
long long dis0[MAX]; int main(int argc, char const *argv[])
{
long long L1, L2, L3, C1, C2, C3;
//freopen("input.txt","r",stdin);
while(scanf("%lld %lld %lld %lld %lld %lld",&L1, &L2, &L3, &C1, &C2, &C3) != EOF)
{
int A, B;
int N; scanf("%d %d",&A,&B);
scanf("%d",&N);
dis0[] = ;
for(int i = ; i <= N; i++) {
scanf("%lld",&dis0[i]);
minCost[i] = inf;
}
if(A > B) {
int temp = A;
A = B;
B = temp;
}
minCost[A] = ;
for(int i = A; i < B; i++) {
for(int j = i + ; j <= B; j++) {
long long int temp;
if(dis0[j] - dis0[i] <= L1) {
temp = C1;
}
else if(dis0[j] - dis0[i] <= L2) {
temp = C2;
}
else if(dis0[j] - dis0[i] <= L3) {
temp = C3;
}
else {
break;
}
long long q = minCost[i] + temp;
if(minCost[j] > q) {
minCost[j] = q;
}
}
}
printf("%lld\n",minCost[B]);
}
return ;
}因为两个站的最大距离不超过L3,所以从A站到j站，中间必然会经过距离j站距离小于L3的某站,故minCost[j]在遍历时中间的分割点必然在这些站之间，所以可以这样化简
最新文章
- webform控件
- Service基础使用
- select、poll、epoll区别总结
- .net之工作流工程展示及代码分享（四）主控制类
- CreateFile函数详解
- hdu 3068最长回文
- css3选择器笔记
- spring beans源码解读
- 连接postgresql数据库
- VARCHAR2(N CHAR)与VARCHAR2(N)的区别[Oracle基础]
- 关于js中window.location.href,location.href,parent.location.href,top.location.href的使用方法
- 开展.net mvc3遇到怪事+解
- UVa 10305 Ordering Tasks (例题 6-15)
- Datatables快速入门开发--一款好用的JQuery表格插件
- Chapter 5 Blood Type——26
- Comet OJ - Contest #2简要题解
- The maximum column size is 767 bytes (Mysql)
- ubuntu12.04 修改登陆用户 为root
- 转-SourceTree注册atlassian账号SIGUP按钮灰色无法注册的问题
- php isset