UVA 10201 Adventures in Moving - Part IV(dp)

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 題意：給定終點距離。和起點到終點之間的加油站位置和每個加油站每升油的價錢，求最少需要花的錢使得到終點後油剩100升。 思路：dp。i作為站點，j作為有多少升油。dp[i][j]表示在第i個站點有j升油所需要花的最少錢，k為在前一個站點加k升油。 狀態轉移方程dp[i][j] = min(dp[i][j], dp[i - 1][j + dis - k] + k * city[i].n)。 代碼：  

#include <stdio.h>  
#include <string.h>  
#include <limits.h>  
#include <math.h>  
#include <algorithm>  
using namespace std;  
  
int t, n, dp[105][205], num, i, j, k;  
char sb[105];  
struct City {  
    int d, n;  
} city[105];  
  
int min(int a, int b) {  
    return a < b ? a : b;  
}  
  
int cmp(City a, City b) {  
    return a.d < b.d;  
}  
int main() {  
    scanf("%d", &t);  
    while (t --) {  
        num = 1;  
        scanf("%d%*c", &n);  
        while (gets(sb) != NULL && sb[0] != '\0') {  
            sscanf(sb, "%d%d", &city[num].d, &city[num].n);  
            num ++;  
        }  
        sort(city + 1, city + num, cmp);  
        for (i = 0; i <= num; i ++)  
            for (j = 0; j <= 200; j ++)  
                dp[i][j] = INT_MAX;  
        dp[0][100] = 0;  
        for (i = 1; i < num; i ++) {  
            int dis = city[i].d - city[i - 1].d;  
            for (j = 0; j <= 200; j ++) {  
                for (k = 0; k <= j; k ++) {  
                    if (j + dis - k <= 200 && dp[i - 1][j + dis - k] !=  INT_MAX) {  
                        dp[i][j] = min(dp[i][j], dp[i - 1][j + dis - k] + k * city[i].n);  
                    }  
                }  
            }  
        }  
        if (dp[num - 1][100 + abs(n - city[num - 1].d)] != INT_MAX && 100 + abs(n - city[num - 1].d) <= 200) {  
            printf("%d\n", dp[num - 1][100 + abs(n - city[num - 1].d)]);  
        }  
        else  
            printf("Impossible\n");  
        if (t) printf("\n");  
    }  
    return 0;  
}