Adventures in Moving - Part IV
题意：
汽车邮箱容量200升，最初有100升油，要求到达终点油箱中的油不少于100升的最小花费，不能到达终点输出Impossible.
汽车走1单位距离消耗1升油。
输入t组数据
输入n表示要求从起点到距离为n的点
输入若干个加油站的a,b,表示加油站距离起点的距离和每升油的价格；
代码：
//dp[i][j]=min(dp[i][j],dp[i-1][j+dis-k]+k*w),dp[i][j]表示到达 //i加油站时还剩j升油，dis表示i到i-1的距离，k（0<=k<=j）表示在i //加油站买多少油，最后要求dp[m][100+n-id[m]]!=inf. #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int inf=0x3f3f3f3f; int dp[110][210],id[110],w[110]; char s[110]; int main() { int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); getchar(); memset(dp,inf,sizeof(dp)); dp[0][100]=0; int cnt=0; while(gets(s)!=NULL&&s[0]!=' '){ cnt++; sscanf(s,"%d %d",&id[cnt],&w[cnt]); if(id[cnt]>n) cnt--; } id[0]=0; for(int i=1;i<=cnt;i++){ int dis=id[i]-id[i-1]; for(int j=0;j<=200;j++){ for(int k=0;k<=j;k++) if(j+dis-k<=200) dp[i][j]=min(dp[i][j],dp[i-1][j+dis-k]+k*w[i]); } } if(n-id[cnt]>100||dp[cnt][100+n-id[cnt]]==inf) printf("Impossible "); else printf("%d ",dp[cnt][100+n-id[cnt]]); if(t) printf(" "); } return 0; } /* 1 500 100 999 150 888 200 777 300 999 400 1009 450 1019 500 1399 */