http://acm.timus.ru/problem.aspx?space=1&num=1031
DP，利用很好的优化，在O(n)时间复杂度内解决
s1,s2,s3分别记录距离在l1,l2,l3内的最远点编号，dp时只需根据这三个点更新
1 #include <iostream>
2 using namespace std;
3 const int OO=1000000001;
4 long long int c1,c2,c3,l1,l2,l3;
5 int n;
6 long long int dis[10011];
7 long long int p[10011];
8 int st,en;
9
10 long long int min(long long int a,long long int b,long long int c){
11 a=a<b?a:b;
12 return a<c?a:c;
13 }
14
15 int main(){
16 scanf("%d %d %d %d %d %d",&l1,&l2,&l3,&c1,&c2,&c3);
17 scanf("%d",&n);
18 scanf("%d %d",&st,&en);
19 if (st>en){
20 long long int m=en;
21 en=st;
22 st=m;
23 }
24 for (int i=2;i<=n;++i) scanf("%d",&dis[i]);
25 int s1,s2,s3;
26 s1=st;s2=st;s3=st;
27 for (int i=st+1;i<=en;++i) p[i]=OO;
28 for (int i=st+1;i<=en;++i){
29 while (dis[i]-dis[s1]>l1) ++s1;
30 while (dis[i]-dis[s2]>l2) ++s2;
31 while (dis[i]-dis[s3]>l3) ++s3;
32 p[i]=min(p[s1]+c1,p[s2]+c2,p[s3]+c3);
33 }
34 cout<<p[en];
35 }
36
posted on 2008-11-04 16:46
Joseph 阅读(197)
评论(0) 编辑 收藏 引用