ZCMU—1869

Problem A: Problem A: Adventures in Moving - Part IV

Time Limit: 1 Sec  

Memory Limit: 128 MB

[

​​Submit​​][

​​Status​​][

​​Web Board​​]

Description

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 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 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 without running out of gas along the way, output "Impossible".

Input

Output

Sample Input

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

Sample Output

450550      

【分析】

基本dp..給你目标距離n，中途有若幹個加油站，給出每個加油站距離起點的距離和該加油的油價（元/升），并且要求在到達目的地時車上還剩餘100升油。

很明顯的dp..f[i][j]表示到第i個加油站剩餘j升油的最少花費,vis[i][j]表示f[i][j]狀态是否可行。

因為要求到目的地時剩餘100升油，直接考慮會比較麻煩，是以可以在最後加一組距離為n+100的加油站。答案就是f[n+100][0]

狀态轉移，對目前f[i][j]枚舉在目前第i個加油站加多少油,保證不超出200升的上限，并且加的油加上原本剩餘的j足夠到達下一個加油站。

【代碼】

#include <stdio.h>
#include <algorithm>
using namespace std;
int n;
int a[20000]={0};
int b[20000]={0};
int f[150][250]={0};
int vis[150][250]={0};
int main()
{
    scanf("%d",&n);
    int len=0;
    while (~scanf("%d%d",&a[len],&b[len])) len++;
    while (a[len-1]>n) len--;
    a[len]=n+100;b[len]=0;
    int rest;
    if (100-a[0]<0) 
    {
        printf("Impossible\n");
        return 0;
    }
    vis[0][100-a[0]]=1;
    f[0][100-a[0]]=0;
    for (int i=0;i<len;i++)
        for (int j=0;j<=200;j++)
            if (vis[i][j])
                for (int k=0;k<=200-j;k++)
                    if (k+j>=a[i+1]-a[i])
                    {
                        rest=k+j-(a[i+1]-a[i]);
                        if (vis[i+1][rest])
                            f[i+1][rest]=min(f[i+1][rest],f[i][j]+k*b[i]);
                        else
                            f[i+1][rest]=f[i][j]+k*b[i],vis[i+1][rest]=1; 
                    }
    if (!vis[len][0]) printf("Impossible\n");
    else printf("%d\n",f[len][0]);
}