经典的DP问题.
#include<iostream> using namespace std; const int INF=1000000001; int l1,l2,l3,c1,c2,c3,n; int dis[10001]; int T[10001]; int main() { int i,j,k; int x,y; scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3); scanf("%d",&n); scanf("%d%d",&x,&y); if(x>y){ k=x; x=y; y=k; } for(i=2;i<=n;i++) scanf("%d",&dis[i]); for(i=x+1;i<=y;i++) T[i]=INF; for(i=x;i<=y;i++) { for(j=i+1;j<=y;j++) { if(dis[j]-dis[i]<=l1) { if(T[j]>T[i]+c1) T[j]=T[i]+c1; } else break; } for(;j<=y;j++) { if(dis[j]-dis[i]<=l2) { if(T[j]>T[i]+c2) T[j]=T[i]+c2; } else break; } for(;j<=y;j++) { if(dis[j]-dis[i]<=l3) { if(T[j]>T[i]+c3) T[j]=T[i]+c3; } else break; } } printf("%d/n",T[y]); return 0; }
