shoken0x

#input
$V = [1, 5, 10, 50, 100, 500]

# 1円玉3枚, 10円玉2枚... 500円玉2枚
$C = [3, 2, 1, 3, 0, 2]
$A = 620 #620円支払う

# $A円を支払う最小の硬貨数を求める

def slove

shoken0x

# input
$n = 4
$w = [2, 1, 3, 2]
$v = [3, 2, 4, 2]
$W = 5

# 重さ$wと価値$vの組み合わせの品物が$n個ある
# 重さの総和が$Wを超えないように選んだときの価値の総和の最大値を求める

def rec(i, j)

shoken0x

# input
$n = 4
$w = [2, 1, 3, 2]
$v = [3, 2, 4, 2]
$W = 5
$dp = Array.new($n + 1, -1){ Array.new($W + 1, -1)}

# 重さ$wと価値$vの組み合わせの品物が$n個ある
# 重さの総和が$Wを超えないように選んだときの価値の総和の最大値を求める

shoken0x

# input
$n = 4
$w = [2, 1, 3, 2]
$v = [3, 2, 4, 2]
$W = 5
$dp = Array.new($n + 1, 0){ Array.new($W + 1, 0)}

# 重さ$wと価値$vの組み合わせの品物が$n個ある
# 重さの総和が$Wを超えないように選んだときの価値の総和の最大値を求める
# 動的計画法 Dynamic Programming

shoken0x

# input
$n = 4
$m = 4
$s = "abcd"
$t = "becd"

# 2つの文字列の、共通部分列の長さの最大値を求める
# 解 3 "bcd"

$dp = Array.new($n + 1, 0){ Array.new($m + 1, 0)}

shoken0x

$heap = []
$size = 0

# heap実装

def push(x)
  # ヒープが空ならRootに追加して抜ける
  return $heap[0] = x if $heap.empty?
  # 追加されたノードが収まるindex
  i = $size += 1

shoken0x

# 二分木探索 Binary Search Tree

class Node
  attr_accessor :val, :left, :right
  def initialize(val)
    @val = val
  end
end

def insert(node, val)

shoken0x

# Union-Find木
MAX_N = 100
$parent = Array.new(MAX_N)
$rank = Array.new(MAX_N, 0)

def init(n)
  n.times do |i|
    $parent[i] = i
  end
end

shoken0x

class Edge
  # 頂点fromから頂点toへのコストcostの辺
  attr_accessor :from, :to, :cost
  def initialize(from, to, cost)
    @from, @to, @cost = from, to, cost
  end
end

MAX_V = 10
$INF = 100_000_000

shoken0x

MAX_V = 10
INF = 100_000_000
$d = Array.new(MAX_V, INF)      # 頂点sからの最短距離
$used = Array.new(MAX_V, false) # すでに使われたかのフラグ
$V = 7

# | i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
# |-----|---|---|---|---|---|---|---|
# | 0   | 0 | 2 | 5 |INF|INF|INF|INF|
# | 1   | 2 | 0 | 4 | 6 |10 |INF|INF|