Language:
Railway tickets
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 2379 Accepted: 823
Description
從1號車站Ekaterinburg到n號車站Sverdlovsk有一條鐵路。
訂票時票價如下
2車站間的距離 -X
價格t
0<X<=L1
C1
L1<X<=L2
C2
L2<X<=L3
C3
由於總總原因，距離超過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
Ural Collegiate Programming Contest 1999
這題就是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為無解情況，可能超過變成負數，線段樹記得開大
[cpp]
#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);
} www.2cto.com
// 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;
}
