九度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;   }