くねくね増加列
携帯だけで書いた下書き:http://ideone.com/36z2ZE
メモ化再帰にもっていけたのは「長くなるように、増え続けるように」(140805追記)のおかげだと思っています。
hena23.rb
#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/7ba11167ea28c929fcf2
#http://nabetani.sakura.ne.jp/hena/ord23snakemoinc/
class Hena23
def initialize(a)
@a=a
@memo={}
end
def dfs(x,y,nprev)
return 0 if x<0||@a[0].size<=x || y<0||@a.size<=y || @a[y][x]<=nprev
return @memo[[x,y]]||=[[-1,0],[1,0],[0,-1],[0,1]].map{|_x,_y|
dfs(x+_x,y+_y,@a[y][x])+1
}.max
end
def run
@a.size.times.lazy.map{|y|
@a[0].size.times.lazy.map{|x|
dfs(x,y,-1)
}.max
}.max
end
end
if $0==__FILE__
STDOUT.sync=true
while gets
p Hena23.new($_.chomp.split('/').map{|e|e.split('').map(&:to_i)}).run
end
end
Author And Source
この問題について(くねくね増加列), 我々は、より多くの情報をここで見つけました https://qiita.com/cielavenir/items/4436c02506da59bc632a著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .