UVA 10201 Adventures in Moving - Part IV

//  [解题方法]
//  dp[i][j]表示到达第i个加油站剩余油量为j时的最小花费
//  特殊地，dp[n][j]表示到达终点剩余油量为j时的最小花费
//  状态转移：(设w[i]为每个加油站的位置，p[i]为油单价)
//    行驶：dp[i][j-(w[i]-w[i-1])] = dp[i-1][j](0<i<=n)
//    加油：dp[i][j] = dp[i][j-1]+p[i](0<i<n)因为n是特意增加的终点，不是加油站

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define LL long long
#define N 105
#define M 205
#define inf 0x3fffffff

int dp[N][M], w[M], p[M];

int main()
{
    char s[105];
    int t, n, i, j, l, m = 200;
    cin >> t;
    getchar();
    while (t--)
    {
        cin >> l;
        getchar();
        n = 1;
        w[0] = 0;
        while (gets(s))
        {
            if (s[0] == 0) break;
            sscanf (s, "%d%d", w+n, p+n);
            ++n;
        }
        w[n] = l;
        for (i = 0; i <= n; i++)
            for (j = 0; j <= m; j++)
                dp[i][j] = inf;
        dp[0][100] = 0;
        for (i = 1; i <= n; i++)
        {
            for (j = w[i]-w[i-1]; j <= m; j++)
                dp[i][j-(w[i]-w[i-1])] = dp[i-1][j];
            if (i < n) for (j = 1; j <= m; j++)
                dp[i][j] = min(dp[i][j], dp[i][j-1]+p[i]);
        }
        int mins = dp[n][100];
        for (j = 101; j <= m; j++)
            if (mins > dp[n][j])
                mins = dp[n][j];
        if (mins == inf) puts ("Impossible");
        else cout << mins << endl;
        if (t) puts ("");
    }
    return 0;
}