#=============================================================================
# A题思路：
#-----------------------------------------------------------------------------
# 其实可以使用下面的方法进行。
# output = 0
# for x1 in 0..10
# for x2 in 0..10
# for x3 in 0..10
# for x4 in 0..10
# for x5 in 0..10
# for x6 in 0..10
# for x7 in 0..10
# for x8 in 0..10
# for x9 in 0..10
# for x10 in 0..10
# if x1+x2+x3+x4+x5+x6+x7+x8+x9+x10 == m
# output += 1
# end
# end
# end
# end
# end
# end
# end
# end
# end
# end
# end
# p output
#-----------------------------------------------------------------------------
# 只写了10支箭的时候，作死向穷举已经把人累得要死了。
# 所以大家不要学习这样的行为。
#-----------------------------------------------------------------------------
# 真·A题思路：
#-----------------------------------------------------------------------------
# 考虑20支箭中最后一箭的成绩，有可能是0到10中间的任何一个。如果这支箭的成绩被
# 确定下来之后，那么我们只需要考虑19支箭所达到的成绩的方式了。
# 所以，仔细想想，下面的关系是成立的。
# 如果用F(n,m)表示用n支箭共射中m环的组合数量，那么应该有：
# F(n,m) = F(n-1,m) + F(n-1,m-1) + ... + F(n-1, m-10)
# 这个就是我们的递推公式，有了它我们就可以写我们的程序了。
# 下面是一个递归算法，如果大家不熟悉递归算法的话，可以改成DP算法，不过那样的
# 话貌似比较浪费内存。
#=============================================================================
module Teijal_Ex1
def self.solve(n,m)
if n * 10 < m || m < 0
return 0
end
if m == 0
return 1
end
output = 0
for i in 0..10
output += self.solve(n-1, m-i)
end
return output
end
end
#=============================================================================
# B题思路：
#-----------------------------------------------------------------------------
# 对于第一只飞来的乌鸦，Te'ijal有两种选择：射击它或者放过它。但是不知道那种选
# 择会带来更好的结果。因此，她必须在两种方法直接进行比较。
# 如果用F(arr)表示当乌鸦的高度分别为arr时（arr是一个数组），Te'ijal最多能击中
# 乌鸦数目。
# 那么应该有：
# F(arr) = [F(arr.shift), 1 + F(arr')].max
# 其中arr.shift表示arr去掉arr[0]之后的数组。（这是放过第一只乌鸦的情况）
# arr'表示去掉arr[0]以及小于它的数字所生成的新数组。（这是射击第一只乌鸦的情况）
#=============================================================================
module Teijal_Ex2
def self.solve(arr)
if arr.empty?
return 0
end
a0 = arr.shift
arr_cpy = arr.reject{|i| i < a0}
return [self.solve(arr), 1 + self.solve(arr_cpy)].max
end
end