采蘑菇（fungus.pas）

之前都是写的递归算法，效率很低，通过这道题，有些理解了非递归的原理了。

代码写的也还算简练。

 

【描述】

萌萌走出山路后，来到一片草地，发现过了草地有巨型蘑菇，于是他准备采摘一些。但是他对保护花草却很重视，他不忍心踩死花草，但为了蘑菇，他只能尽量少踩死几株。现在，草地上也像一条路，上面有n个点，第N个点就是巨型蘑菇所在地（上面没草），每个点上都有i株小草或j株蘑菇（也就是说有蘑菇就没有草），他每次最多跨越k步。

现在请为他选择一条路，在踩死尽量少的小草下，去采蘑菇。

P.S：默认出发点为：1，结束点为：N；

【输入格式】

第一行2个数：

n（表示这条路的长度），k（每次最多跨越数）

接下来第二行，n个数：

A[1],a[2],a[3]…a[n]（就是相应株数的小草，例如：

0 0 1 2 0【这是说第3个点有1株草，第4个点有2株草】)

【输出格式】

一个数，最少踩到的小草株数：m

【输入样例】

5 2

0 1 1 2 0

【输出样例】

1

（只踩到了第3株）

【数据范围】

N,k<=10000;

A[i]<=100;

 

 

my @data = (0,1,1,2,4,0);
my $steps = 2;
my @res;

for (my $i = 0; $i<@data -2; $i++){
    for(1..$steps){
        my $cur = $res[$i] + $data[$i+$_];
     if($res[$i+$_] == 0 or $res[$i+$_]>$cur){
            print $i+$_." = $cur \n";
            $res[$i+$_] = $cur;
        }
    }
}
print $res[@data-1];