首页 > 代码库 > UVa 10201 Adventures in Moving - Part IV
UVa 10201 Adventures in Moving - Part IV
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 //freopen("D:\\txt.txt", "r", stdin);18 int T;19 gets(s);20 sscanf(s, "%d", &T);21 gets(s); //吃掉空行22 while (T--)23 {24 gets(s);25 sscanf(s, "%d", &length);26 num = 0;27 a[0] = 0;28 while (gets(s) != NULL)29 {30 if (s[0] == ‘\0‘) break;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; //起点，油量为200，花费为040 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++) //加了k升油后此时的油量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\n");53 else54 printf("%d\n", d[num][100 + length - a[num]]);55 if (T) printf("\n");56 }57 return 0;58 }
UVa 10201 Adventures in Moving - Part IV
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。