uva 10201 Adventures in Moving – Part IV题目大意：借了一辆车，，车里有100单位的油。要到达N米外的目的地（每走一米消耗一个单位的油），在这一段路程中，有若干个加油站，给出的数据是每个加油站的位置和加一单位油的价格。要求到达目的地且剩下100单位油的最小消费。（到达不了则输出Impossible）解题思路：dp[i][j]数组代表的是第i个加油站油量为j的最小费用。
状态转移方程：
;ll;const int INF = 1000000000;struct GAS{int mile, money;}g[N];int cmp(GAS a, GAS b) {return a.mile < b.mile;}char s[100];int n, cnt, dp[N][M];void DP() {for (int i = 1; i <= cnt; i++) {int dis = g[i].mile – g[i – 1].mile;for (int j = 0; j + dis <= 200; j++) {if (dp[i – 1][j + dis] < dp[i][j]) {dp[i][j] = dp[i – 1][j + dis];}}for (int j = 1; j <= 200; j++) {int temp = INF;for (int k = 0; k < j; k++) {int sum = dp[i][k] + (j – k) * g[i].money;if (sum < temp) temp = sum;}if (temp < dp[i][j]) {dp[i][j] = temp;}}}}int main() {int T;scanf(“%d\n”, &T);while (T–) {cnt = 0;scanf(“%d%*c”, &n);while (gets(s) != NULL && s[0] != 0) {++cnt;sscanf(s, “%d %d”, &g[cnt].mile, &g[cnt].money);if (g[cnt].mile < 0 || g[cnt].mile > n) cnt–;}g[0].mile = 0;for (int i = 0; i <= cnt; i++) {for (int j = 0; j <= 200; j++) {dp[i][j] = INF;}}dp[0][100] = 0;DP();if (n – g[cnt].mile > 100 || dp[cnt][100 + n – g[cnt].mile] == INF) {printf(“Impossible\n”);} else {printf(“%d\n”, dp[cnt][100 + n – g[cnt].mile]);}if (T) printf(“\n”);}return 0;}
我不敢说我可以忘却，或者勇敢，坚强，等等等等一切堂皇而陈旧的字眼。
