POJ 2355 Railway tickets
题意：解题过程：AC代码：
POJ 2355 Railway tickets
题目传送门
题意：
你需要从s点做车到t点，车在行驶距离不同时价格不同，如果距离比0大且比l1小，那么价格为c1如果距离比l1大且比l2小，那么价格为c2，如果距离比l2大且比l3小，那么价格为c3，但一辆车的行驶距离不能超过l3，一共有n个坐车点，你可以在这些坐车坐车，给出你这些坐车点的位置，问你从s点到t点最小花费是多少。
解题过程：
比较简单的DP，f[i]表示坐到i点的最小花费然后枚举i点之前的j点，按照距离选取价格进行转移。不过唯一需要注意的点就是题目中没有保证s
AC代码：
#pragma GCC optimize (3)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=
10005;
int l1,l2,l3,c1,c2,c3;
int n;
int s,t;
int dis[maxn],d[maxn];
int f[maxn];
int main() {
scanf(
"%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3);
scanf(
"%d",&n);
scanf(
"%d%d",&s,&t);
if(s>t)swap(s,t);
dis[
1]=
0;
d[
1]=
0;
for(
int i=
2;i<=n;i++) {
scanf(
"%d",&dis[i]);
d[i]=dis[i]-dis[i-
1];
}
for(
int i=
0;i<=n;i++) {
f[i]=
0x3f3f3f3f;
}
f[s]=
0;
for(
int i=s+
1;i<=t;i++) {
ll dd=d[i];
for(
int j=i-
1;dd<=l3&&j>=s;dd+=d[j],j--){
int cost;
if(
0<dd&&dd<=l1)cost=c1;
if(l1<dd&&dd<=l2)cost=c2;
if(l2<dd&&dd<=l3)cost=c3;
f[i]=min(f[i],f[j]+cost);
}
}
printf(
"%d\n",f[t]);
return 0;
}
本人蒟蒻OIer一枚，欢迎加QQ：840776708一起学习蛤。
转载于:https://www.cnblogs.com/Apocrypha/p/9433667.html
