3
已解决
新手光能
1296 如何乘车
题目描述 Description
某条街上每一公里就有一汽车站，乘车费用如下：
公里数12345678910费用122131404958697990101
而一辆汽车从不行驶超过10公里。某人想行驶n公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10公里的费用比1公里小的情况是允许的）。
输入描述 Input Description
共两行，第一行为10个不超过200的整数，依次表示行驶1-10公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公里数。
输出描述 Output Description
仅一行包含一个整数，表示该测试点的最小费用。
样例输入 Sample Input
12 21 31 40 49 58 69 79 90 101
15
样例输出 Sample Output
147
数据范围及提示 Data Size & Hint
n<=200
注：用动态规划做。
2
已采纳
资深天翼
最基础的完全背包问题，只不过这个是求方法数。
一开始f数组要赋得很大。
f[0]=0;边界
for(int i=1; i<=10; i++)
{
for(int j=i; j<=n; j++)
f[j]=min(f[j],f[j-i]+a[i]);
}
最后输出f[n]
0
缔造者之神
1
