题目描述：
某条街上每一公里就有一汽车站，乘车费用如下表：
公里数 --------- 费用
1 ---------------- 12 2 ---------------- 21 3 ---------------- 31 4 ---------------- 40 5 ---------------- 49 6 ---------------- 58 7 ---------------- 69 8 ---------------- 79 9 ---------------- 90 10 ---------------- 101（重新排版很累人的……）而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。
编一程序：
从文件BUSSES.IN中读入对乘车费用的描述；算出最小的价格；把结果写入文件BUSSES.OUT中。
输入：
输入文件共两行，第一行为10个不超过100的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公里数。
输出：
输出文件仅一行包含一个整数，表示该测试点的最小费用。
样例输入：
12 21 31 40 49 58 69 79 90 101
15
样例输出：
147
首先分析一下题意：这个小家伙要坐车，每走一公里就会有相应的费用，所以给出一个距离，求花费费用的最小值。
那么可以用贪心的办法。但是——本标签是DP，所以还是用DP的比较好吧……先上代码：#include#include #include #include using namespace std; int f[21],dp[111]; int n; int main() { memset(dp,127,sizeof(dp)); for(int i=1;i<=10;i++) scanf("%d",&f[i]); scanf("%d",&n); dp[0]=0; dp[1]=f[1]; for (int i=2;i<=n;i++) { dp[i]=dp[i-1]+f[1]; for (int j=2;j<=10 && j<=i;j++) dp[i]=min(dp[i],dp[i-j]+f[j]); } printf("%d",dp[n]); return 0; }
这里有好多东西啊！！！
先看那个memset，此处的“127”代表的是INF，所以你不需要担心dp的值啦；但是——你会看到main里有一个dp[0]=0,这就是为了补充那个memset，因为memset把0的值也给复制过来了，所以必须得初始化dp[0]的值。然后，下面还有一个dp[1]=f[1]，意思就是说当dp[]=1的时候，它就等于f[1]的值（反正很好理解，这里就不多做解释了……）。还有！！！千万别忘了，你求的是min！！！不是max！！！（如果您要用k来更新的话，也不要忘了把k整的很大啊……）