?

题目大意:一辆车要走D距离，然后它有个200L油箱，并且一开始有100L，现在给你一路上你会遇到的加油站，和这个加油站每升油的价钱，要求你最后到终点的时候油需要大于等于100L，问你加油最少的费用。如果到达不了目标地点就输出Impossible。

?

解题思路：首先要先到达这个加油站，然后就相当这个加油站你选不选择加油，选择加油了那么又要加多少油。dp【j】【i】代表到达第i个加油站还有jL油，dp【j】【i】 = MIn（dp【j +d【i】【l】】【l】）；d【i】【l】代表第i个加油站和第l个加油站的距离，意思就是看当到达这个加油站，应该是从哪个加油站加了油出发这样花费最少。然后就是在这个加油站加多少的油的问题。

都是从0出发到达D这个位置，那么就在这两个位置加上加油站，然后用price来表示这个加油站是否真是存在。真实存在才可以加油。初始条件dp【0】【100】 = 0；

?

代码：

?

#include 
  
   
#include 
   
     const int N = 205; const int INF = 0x3f3f3f3f; int n; int gas[N][2]; int f[N][N]; int d[N][N]; char str[N]; int Min (const int a, const int b) { return a < b ? a: b; } void init () { for (int i = 0; i < n; i++) for (int j = i; j < n; j++) d[i][j] = gas[j][0] - gas[i][0]; for (int i = 0; i < n; i++) for (int j = 0; j <= 200; j++) f[i][j] = INF; f[0][100] = 0; } int main () { int t; int D; scanf (%d, &t); while (t--) { scanf (%d%*c, &D); n = 1; gas[0][0] = 0; while (gets(str) != NULL && str[0] != '') { sscanf (str,%d%d, &gas[n][0], &gas[n][1]); n++; } /* for (int i = 0; i < n; i++) printf (%d %d , gas[i][0], gas[i][1]);*/ if (gas[n - 1][0] != D) { gas[n][0] = D; gas[n][1] = 0; n++; } init(); for (int i = 1; i < n; i++) { for (int j = 0; j <= 200; j++) { for (int l = i - 1; l >= 0; l--) { //哪种方式到达最省 if (j + d[l][i] <= 200) f[i][j] = Min (f[i][j], f[l][j + d[l][i]]); else break; } if (gas[i][1] && f[i][j] != INF) {//加多少油（前提能够到达，并且这个加油站是真的） for (int k = j + 1; k <= 200; k++) f[i][k] = f[i][j] + (k - j) * gas[i][1]; } } } int ans = INF; for (int i = 100; i <= 200; i++) ans = Min (ans, f[n - 1][i]); if (ans != INF) printf (%d , ans); else printf (Impossible ); if (t) printf ( ); } return 0; }
   
  

?

?