24h購物| | PChome| 登入
2013-04-02 08:44:04| 人氣1,195| 回應1 | 上一篇 | 下一篇

[UVA][dp] 10201 - Adventures in Moving - Part IV

推薦 0 收藏 0 轉貼0 訂閱站台

Problem A: Adventures in Moving - Part IV

To help you move from Waterloo to the big city, you are considering renting a moving truck. Gas prices being so high these days, you want to know how much the gas for such a beast will set you back.

The truck consumes a full litre of gas for each kilometre it travels. It has a 200 litre gas tank. When you rent the truck in Waterloo, the tank is half full. When you return it in the big city, the tank must be at least half full, or you'll get gouged even more for gas by the rental company. You would like to spend as little as possible on gas, but you don't want to run out along the way.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Input is all integers. The first integer is the distance in kilometres from Waterloo to the big city, at most 10000. Next comes a set of up to 100 gas station specifications, describing all the gas stations along your route, in non-decreasing order by distance. Each specification consists of the distance in kilometres of the gas station from Waterloo, and the price of a litre of gas at the gas station, in tenths of a cent, at most 2000.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Output is the minimum amount of money that you can spend on gas to get you from Waterloo to the big city. If it is not possible to get from Waterloo to the big city subject to the constraints above, print "Impossible".

Sample Input

1

500
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399

Output for Sample Input

450550

dp[i][j] 表示到第 i 站的剩餘 j 油量。
最簡單的方程 dp[i][j] = min(dp[i-1][j-dis((i-1)->(i))], min(dp[i][j-k]+k*p[i]))

想一想,真的需要枚舉 k 嗎?一次加 k 的油量?

其實只要跟 dp[i][j-1] + p[i] 就可以了,跟前一個狀態比加一升就可以了。


#include <stdio.h>
#include <algorithm>
#define oo 100000000
using namespace std;

int main() {
int t, D;
int i, j, dp[105][205];
char s[105];
scanf("%d", &t);
while(getchar() != '\n');
gets(s);
while(t--) {
scanf("%d", &D);
while(getchar() != '\n');
int d[105], p[105], n = 1;
d[0] = 0, p[0] = 0;
while(gets(s) && s[0]) {
sscanf(s, "%d %d", &d[n], &p[n]);
n++;
}
d[n] = D, p[n] = oo;
for(i = 0; i <= n; i++)
for(j = 0; j <= 200; j++)
dp[i][j] = oo;
dp[0][100] = 0;
for(i = 1; i <= n; i++) {
int dis = d[i]-d[i-1];
for(j = dis; j <= 200; j++)
dp[i][j-dis] = min(dp[i][j-dis], dp[i-1][j]);
for(j = 1; j <= 200; j++)
dp[i][j] = min(dp[i][j], dp[i][j-1]+p[i]);
}
int ans = oo;
for(i = 100; i <= 200; i++)
ans = min(ans, dp[n][i]);
if(ans == oo)
puts("Impossible");
else
printf("%d\n", ans);
if(t)
puts("");
}
return 0;
}
 

台長: Morris
人氣(1,195) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][maxflow] 563 - Crimewave
此分類上一篇:[UVA][字串處理] 10146 - Dictionary

美國黑金
很不錯的分享~!
2020-02-21 02:16:58
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文