15
题目意思别理解错了，走一公里12，两公里32...是分别独立的
一开始我理解成走两公里是建立在走完一公里的基础上
理解好意思就是一个裸完全背包了，容量是旅程的公里数，花费是坐车走的公里数，价值是做相应公里数的坐车的费用，每个相应的公里数可以无限取，求恰好完成的旅程的最少车费
这里要注意下初始化，详见《背包九讲》
1 #include<cstdio> 2 #include<cstring> 3 #include<stdlib.h> 4 #include<algorithm> 5 #include<iostream> 6 using namespace std; 7 int dp[600]; 8 int v[105]; 9 int main() 10 { 11 int i,j,m; 12 memset(dp,0x3f3f3f3f,sizeof(dp)); 13 memset(v,0,sizeof(v)); 14 15 for(i=1;i<=10;i++) 16 scanf("%d",&v[i]); 17 scanf("%d",&m); 18 19 dp[0]=0; 20 for(i=1;i<=10;i++) 21 for(j=i;j<=m;j++) 22 dp[j]=min(dp[j],dp[j-i]+v[i]); 23 24 printf("%d\n",dp[m]); 25 return 0; 26 }
TYVJ 公路乘车 完全背包（水题）,布布扣,bubuko.com
原文：http://www.cnblogs.com/clliff/p/3879068.html
