猴子上楼梯的c语言详细原代码及解析

来源：百度知道 编辑：UC知道 时间：2024/05/28 19:01:44
在楼梯的每个阶梯上都有一个正整数数据，猴子上楼梯时可以一次上1个、2个，……，k个阶梯，猴子上楼梯的总代价为它 所经过的阶梯数值之和，问猴子怎样上楼梯才能使上楼梯的总代价最少。
输入：
第1行 为n，k，分别表示楼梯的总阶数
第2行为用空格分开的n个正整数，分别表示第1、2、……、n个阶梯的数值。
输出：
上楼梯的最少的代价。

20分……
只能给你思路了

用数组a[i]记录猴子上到第i个阶梯时最少代价，b[i]为所输入的阶梯上的正整数数据

用两层循环，

第一层循环i是从1到n，对每层阶梯进行扫描

第二层循环j是从1到k，如果a[i+j]<a[i]+b[i+j]即将a[i+j]更新为a[i]+b[i+j]

a[i]+b[i+j]的意思是在第i层阶梯的最少代价加上第i+j层的那个数据，
如果小于在第i+j层的暂时最小代价（因为最小值还没确定），
那么就更新第i+j层的代价，使它变得更小

这样一步步递推，就能得到a[n]的最小代价

#include <stdio.h>
int n,k;
int cost[100];
int best(int curstep)
{
double use=0;int stp=1;
for(int i=1;i<=k;++i)
if(use<(double)i/cost[curstep+i])
{
use=(double)i/cost[curstep+i];
stp=i;
}
return stp;
}/*步长÷代价越大越好*/
int main()
{
int i,all=0,curstep=0;
scanf("%d %d",&n,&k);
for(i=1;i<=n;++i) scanf("%d",&cost[i]);

for(i=1;curstep+k<n;++i)
{
curstep+=best(curstep);
all+=cost[curstep];
}/*若curstep+k<