九度OJ 1086 动态规划之《最小花费》——11年清华机试真题


 
[cpp]  
//九度OJ 1086 动态规划之《最小花费》  
//http://ac.jobdu.com/problem.php?pid=1086  
#include<stdio.h>  
#define MAXN 2211686018427387904  
#define MAXS 30000  
long long l1,l2,l3,c1,c2,c3,rout[MAXS];  
long long spe(int start,int end)//输入起始点与终点的站号，输出这俩站之间的花费。  
{  
    int temp=rout[end]-rout[start];  
    if(temp<=l1)return c1;  
    if(temp<=l2)return c2;  
    if(temp<=l3)return c3;  
    return MAXN;  
}  
int main()  
{  
    long long temp,i,j,a,b,n,spend[MAXS];  
    while(~scanf("%lld %lld %lld %lld %lld %lld",&l1,&l2,&l3,&c1,&c2,&c3))  
    {  
        for(i=temp=0;i<MAXS;i++)rout[i]=spend[i]=MAXN;  
        scanf("%lld %lld",&a,&b);  
        scanf("%lld",&n);  
        rout[1]=0;  
        for(i=2;i<=n;i++)scanf("%lld",&rout[i]);  
        for(i=a,spend[a]=0;i<b;i++)  
        {  
            for(j=i+1;rout[j]-rout[i]<=l3&&j<MAXS;j++)//保证下面spe函数的输入俩站间距离是小于等于l3的。  
            {  
                temp=spe(i,j);  
                if(spend[j]>spend[i]+temp)spend[j]=spend[i]+temp;  
            }  
        }  
        printf("%lld\n",spend[b]);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,