10201 - Adventures in Moving - Part IV

[cpp] 
描述：i表示第幾個加油站，j表示在第i個加油站時剩余的油量，k表示在第i個加油站要加的油量 
#include <cstdio>  
#include <cstdlib>  
#include <cstring>  
int v[110][210],arr[110][2]; 
int min(int x,int y) 
{ 
    return x>y?y:x; 
} 
int main() 
{ 
  //  freopen("a.txt","r",stdin);  
    int t,n,len,sum,c; 
    char str[110]; 
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        len=1; 
        getchar(); 
        while(gets(str)&&str[0]!='\0') 
        { 
            sscanf(str,"%d%d",&arr[len][0],&arr[len][1]); 
            if(arr[len][0]<=n) len++; 
        } 
        memset(v,0x7f,sizeof(v)); 
        v[0][100]=arr[0][0]=0; 
        for(int i=1; i<len; i++) 
            for(int j=0; j<=200; j++) 
            { 
                c=arr[i][0]-arr[i-1][0]; 
                if(j-c>=0)for(int k=0; j+k-c<=200; k++) 
                        v[i][j+k-c]=min(v[i][j+k-c],v[i-1][j]+k*arr[i][1]); 
            } 
        arr[0][1]=sum=v[0][0]; 
        c=n-arr[len-1][0]; 
        for(int i=100; i<=200; i++) 
        { 
            if(arr[len-1][1]!=v[0][0]&&sum>arr[len-1][1]*c+v[len-1][i]&&i+c<=200) 
                sum=arr[len-1][1]*c+v[len-1][i]; 
        } 
        if(sum==v[0][0]) printf("Impossible\n"); 
        else printf("%d\n",sum); 
        if(t) puts(""); 
    } 
    return 0; 
}