https://vjudge.net/problem/UVA-10201
题意：
给出到达终点的距离和每个加油站的距离和油费，初始油箱里有100升油，计算到达终点时油箱内剩100升油所需的最少花费。
思路：
我们用d[i][j]来表示车子在第 i 个加油站时还剩 j 升油量的最小花费。
先说一下转移方程吧，d[i][j] = min(d[i][j], d[i - 1][j + l - k] + k*b[i])，k代表的是在 i 这个加油站所加的油量，加了之后的总油量就是 j 。
需要注意的是，油箱的容量只有200升，所以j+l-k（第 i-1 个加油站的油量）必须小于等于200。
最后的判断，如果目的地距离最后那个加油站大于了100，那最终肯定是没办法剩100升的，这时可以直接“Impossible”。
本题的输入也是很麻烦，每次都需要整行读入才行。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 7 const int INF = 100000000; 8 9 char s[100]; 10 int length; 11 int num; 12 int a[105], b[105]; 13 int d[105][205]; //d[i][j]表示在第i站还剩j汽油时的最少费用 14 15 int main() 16 { 17 int T; 18 gets(s); 19 sscanf(s, "%d", &T); 20 gets(s); //吃掉空行 21 while (T--) 22 { 23 gets(s); 24 sscanf(s, "%d", &length); 25 num = 0; 26 a[0] = 0; 27 while (gets(s)) 28 { 29 if (s[0] == ' ') break; 30 num++; 31 sscanf(s, "%d %d", &a[num], &b[num]); 32 //cout << a[num] << " " << b[num] << endl; 33 if (a[num] > length) num--; //距离大于目的地的站不用考虑 34 } 35 36 for (int i = 0; i <= num; i++) 37 for (int j = 0; j <= 200; j++) 38 d[i][j] = INF; 39 d[0][100] = 0; 40 41 for (int i = 1; i <= num; i++) 42 { 43 int l = a[i] - a[i - 1]; 44 for (int j = 0; j <= 200; j++) 45 { 46 for (int k = 0; k <= j; k++) 47 if (j + l - k <= 200) 48 d[i][j] = min(d[i][j], d[i - 1][j + l - k] + k*b[i]); 49 } 50 } 51 if (length - a[num]>100 || d[num][100 + length - a[num]] == INF) 52 printf("Impossible "); 53 else 54 printf("%d ", d[num][100 + length - a[num]]); 55 if (T) printf(" "); 56 } 57 return 0; 58 }