uva10201 - Adventures in Moving - Part IV（01背包）

uva10201 - Adventures in Moving - Part IV（01背包）

題目大意:一輛車要走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;
}