内容目录
|
Language:
Railway tickets
Description
从1号车站Ekaterinburg到n号车站Sverdlovsk有一条铁路。
 订票时票价如下
由于总总原因，距离超过L3的车票不能定。
现在你打算从s号车站乘铁路到t号车站，求最小费用。
Input
第一行有6个数 L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, 1 <= C1 < C2 < C3 <= 10^9)
第二行为车站数N (2 <= N <= 10000)
第三行为s和t，表示起点和终点.
接下来n-1行，表示从第1好车站到第i(1<i<=n)号车站的距离（保证是升序）.
Output
仅一行，为最小费用(<10^9)
Sample Input 3 6 8 20 30 40 7 2 6 3 7 8 13 15 23 Sample Output 70 Source |
这题就是Dp
显然F[i]=F[j]+c[k](j<i,a[j]-a[i]<=l[k],1<=k<=3) F[i]表示从起点s到车站i的最小费用。
用显然j单调递增，可用指针向后推（O(n)）
注意判断INF为无解情况，可能超过变成负数，线段树记得开大
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (20000+10)
#define INF (2139062143)
int l[4],c[4],n,a[MAXN],st,en;
struct SegMentTree
{
int t[MAXN*10],n,M;
SegMentTree(){}
SegMentTree(int _n):n(_n)
{
M=1;while (M-2<n) M<<=1;
memset(t,127,sizeof(t));
}
void update(int x)
{
for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
}
void insert(int x,int c)
{
x+=M;
if (t[x]>c)
{
t[x]=c;//cout<<endl<<'I'<<x<<' '<<c<<endl;
update(x);
}
}
int find(int l,int r)
{
if (l>r) return INF;
l=l-1+M;r=r+1+M;
int ans=INF;
while (l^r^1)
{
if (~l&1) ans=min(ans,t[l+1]);
if (r&1) ans=min(ans,t[r-1]);
l>>=1;r>>=1;
}
return ans;
}
}t;
void push(int &j,int L,int i)
{
while (a[i]-a[j]>L) j++;
}
int main()
{
scanf("%d%d%d%d%d%d%d",&l[1],&l[2],&l[3],&c[1],&c[2],&c[3],&n);
t=SegMentTree(n);
scanf("%d%d",&st,&en);if (st>en) swap(st,en);
if (st==en) {cout<<"0"<<endl;return 0; }
a[1]=0;
for (int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
}
int j[4]={st,st,st,st};
t.insert(st,0);
for (int i=st+1;i<=en;i++)
{
int value=INF;
for (int k=1;k<=3;k++)
{
push(j[k],l[k],i);
// cout<<j[k]<<' ';
int p=t.find(j[k],i-1);
if (p<INF) p+=c[k];
value=min(value,p);
}
// cout<<value<<' '<<endl;
t.insert(i,value);
// for (int i=1;i<=t.M*2;i++) if (t.t[i]-INF) cout<<i<<' '<<t.t[i]<<' ';
// cout<<endl;
}
cout<<t.find(en,en)<<endl;
return 0;
}