最小花费[THU@2011研究生机试题]

//@Jobdo DY问题
 1#include<iostream>
 2#include<cstdlib>
 3#include<algorithm>
 4using namespace std;
 5
 6#define INF -1//定义为无穷大
 7typedef long long int T;
 8
 9T **m;
10T L[4];//距离
11T C[4];//花费
12T A,B,n;
13T *v;//第一站到其他站的距离
14
15T MinCost();
16int main()
17{    
18    while(cin>>L[1]>>L[2]>>L[3]){//输入三种路程
19        for(int i=1;i<=3;i++)// 输入三种票价
20            cin>>C[i];        
21        cin>>A>>B>>n;
22        
23        if(A==B){
24            cout<<0<<endl;
25            continue;
26        }
27        if(A>B)
28            swap(A,B);
29        v=(T*)malloc(sizeof(T)*(n+1));
30        v[1]=0;//第一站到第一站的距离
31        for(T i=2;i<=n;i++)//读入第一站到其他各站的距离            
32            cin>>v[i];        
33        cout<<MinCost()<<endl;
34                free(v);
35    }//end while
36
37    return 0;
38}
39T MinCost()
40{
41    m=(T **)malloc(sizeof(T *)*(B+10));//+10多分配几个空间
42    for(int i=0;i<B+10;i++)
43        m[i]=(T *)malloc(sizeof(T)*(B+10));
44    
45    T len=B-A+1;//AB之间的站数
46    for(T i=A;i<=B;i++)
47        m[i][i]=0;//m[i][j]:i站到j站的最小花费
48        
49    for(T pace=2;pace<=len;pace++)
50    {
51        for(T pos=A;pos<=B-pace+1;pos++)
52        {
53            T distance=v[pace+pos-1]-v[pos];
54            if(distance>=0 && distance<=L[1])
55                m[pos][pace+pos-1]=C[1];
56            else if(distance>L[1] && distance<=L[2])
57                m[pos][pace+pos-1]=C[2];
58            else if(distance>L[2] && distance<=L[3])
59                m[pos][pace+pos-1]=C[3];
60            else if(distance>L[3])
61                m[pos][pace+pos-1]=-1;
62            
63            for(T k=pos+1;k<pos+pace-1;k++)
64            {
65                T tp=m[pos][k]+m[k][pos+pace-1];
66                if(m[pos][pace+pos-1]==-1 || tp<m[pos][pace+pos-1])
67                    m[pos][pace+pos-1]=tp;
68            }
69        }
70    }
71    T result=m[A][B];
72    for(T t=0;t<B+10;t++)
73        free(m[t]);
74    free(m);
75    
76    return result;
77}

posted on 2012-02-22 11:40 DjvuLee 阅读(107) 评论(0)  编辑 收藏 引用 所属分类: 算法设计


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2012年2月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

统计

常用链接

留言簿

随笔分类(13)

随笔档案(19)

文章分类(2)

文章档案(1)

搜索

最新评论

评论排行榜