斑的家

CODE 有點丑= =''

#include<iostream>
#include<vector>
#define STATION 101
#define FUEL    201
#define INF 100000000
int dp[STATION][FUEL];
/*
 * PROBLEM : given starting point , arrival point, and lots of patroleum stations and their prices.
 * the tank capacity is 200, find the smallest cost.
 * SOLUTION: dynamic programming
 */
using namespace std;
struct point
{
    point(){}
    point(int a,int b):pos(a),price(b){}
    int pos;
    int price;
};
int main()
{
    int cas,dist,i,j,k;
    char l[100];
    cin>>cas;
    while(cas--)
    {
        for(i = 0 ; i< STATION;i++)
            for(j = 0 ;j < FUEL ;j++)
            dp[i][j] = INF;
        cin>>dist;
        cin.get();
        vector<point> v;
        while(fgets(l,100,stdin))
        {
            int a,b;
            if(l[0]=='\n')break;
            sscanf(l,"%d%d",&a,&b);
            v.push_back(point(a,b));
        }
        // goto first patroleum station first
        // cut off station farther than dist
        bool yes = true;
        if(v.size()==0)
        {
            if(dist==0)cout<<0<<endl;
            else
            cout<<"Impossible"<<endl;
            if(cas)cout<<endl;
            continue;
        }
        int station = v.size();
        int fuel = 100 - v[0].pos;
        if(fuel<0)cout<<"Impossible"<<endl;
        else
        {
            
            
            dp[0][fuel] = 0;
            for(i = 0 ; i < (station-1) ; i++) // current station
            {
                    int d = v[i+1].pos - v[i].pos;
                    if(d > 200){yes = false;goto L;}    
                for(j = 0 ;j <= 200 ;j++) // remaining patroleum
                    for(k = 0 ; (k +j)<=200;k++) // add how many patroleum
                    {
                        if(j+k < d)continue;
                        
                        dp[i+1][j+k-d] = min(dp[i+1][j+k-d],dp[i][j]+v[i].price*k);            
                    }
            }
            L:
            if(yes){
             // now at the last station, determine
                 if(dist - v[station-1].pos > 100)cout<<"Impossible"<<endl;
                else
                {
                    int ans = INF;
                     for(j = 0 ;j < 200 ; j++)
                    {
                        int need = dist - v[station-1].pos + 100-j;
                        if(need < 0)need = 0;
                        ans = min(ans,dp[station-1][j]+v[station-1].price*need);
                    }
                    cout<<ans<<endl;
                }
            }
            else cout<<"Impossible"<<endl;
            
        }
        if(cas)cout<<endl;
    }
    return 0;
}