2014-08-01から1ヶ月間の記事一覧
書きました。 APIを使うところは省略しています critics = { 'Lisa Rose' => { 'Lady in the Water' => 2.5, 'Snakes on a Plane' => 3.5, 'Just My Luck' => 3.0, 'Superman Returns' => 3.5, 'You, Me and Dupree' => 2.5, 'The Night Listener' => 3.0 },…
今日というか今日と昨日 単一始点最短経路問題(ベルマンフォード) ある頂点sからのすべての頂点の最短経路 d[j] > d[i] + costこの条件を1度使っただけでは明らかに最短にならないので update変更がなくなるまでループを繰り返す INF = 100_000 G = [[INF, …
彩色問題 アリ本の93ページ 隣接したりノードが同じ色にならないように色をぬる。 今回は2色で塗ることができるかという問題 特に2色でぬれるグラフを2部グラフという コードで言うと0が塗ってないノードなので下の2つを繰り返す感じ 隣接したノードjが0…
分割数はいまいちわかっていない 最長増加部分列問題 自分(i)より小さい部分問題を解いていけばできる N = 5 A = [4, 2, 3, 1, 5].freeze $dp = Array.new(N, 1) def solve N.times do |i| i.times do |j| $dp[i] = [$dp[j] + 1, $dp[i]].max if A[i] > A[j]…