#--------- 入力例1 ----------
# ノードの数
n = 4
# 全エッジ（ x → y ）
lst = [(1, 2),
       (1, 3),
       (3, 2),
       (2, 4),
       (3, 4)]
#--------- 入力例2 ----------
# # ノードの数
# n = 6
# # 全エッジ（ x → y ）
# lst = [(2, 3),
#        (4, 5),
#        (5, 6)]
#--------- 入力例3 ----------
# # ノードの数
# n = 5
# # 全エッジ（ x → y ）
# lst = [(5, 3),
#        (2, 3),
#        (2, 4),
#        (5, 2),
#        (5, 1),
#        (1, 4),
#        (4, 3),
#        (1, 3)]
#----------------------------
from collections import defaultdict 

# トポロジーソートを行うクラス
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self, v, visited,stack): 
        visited[v] = True
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
        return stack

g = Graph(n + 1)    # 0スタートなので頂点を１つ多めに
for a, b in lst:
    g.addEdge(a, b)     # 有向パス追加

print ("トポロジカルソートの結果：", g.topologicalSort())

# トポロジカルソート順に通過数をカウント
memo = {}   # カウント（キー：頂点番号、バリュー：通過数）
for x in list(g.topologicalSort()):
    for a, b in lst:
        if x == a:
            memo[b] = memo.get(a, 0) + 1

print('解：', max(memo.values()))

#---------- 入力例1 ----------
a = 'axyb'
b = 'abyxb'
#---------- 入力例2 ----------
# a = 'aa'
# b = 'xayaz'
#---------- 入力例3 ----------
# a = 'a'
# b = 'z'
#---------- 入力例4 ----------
# a = 'abracadabra'
# b = 'avadakedavra'
#-----------------------------
# メモ化テーブル
memo = {}
x = ''
for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        # print(i,j,a1,b1)
        if a1 == b1:
            # print('  #', a1,i,j)
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))
print('長さ：', memo[(len(a), len(b))])

# メモ化テーブルの値を見ながら、今いるノード (i,j)(i,j) がどのノードから更新されて来たのかを特定する
i, j = len(a), len(b)

res = ''    # 求める最長の文字列   
while i > 0 and j > 0:
    if memo.get((i, j), 0) == memo.get((i - 1, j), 0):    # (i-1, j) -> (i, j) と更新されていた場合
        i -= 1
    elif memo.get((i, j), 0) == memo.get((i, j - 1), 0):  # (i, j-1) -> (i, j) と更新されていた場合
        j -= 1
    else:                           # (i-1, j-1) -> (i, j) と更新されていた場合
        res = a[i - 1] + res        # 求める文字列を復元する　a[j - 1]でも可
        i -= 1
        j -= 1
print('解：', res)

#--------- 入力例1 ----------
w = 8
items = [{'weight':3, 'value':30},
         {'weight':4, 'value':50},
         {'weight':5, 'value':60}]
#--------- 入力例2 ----------
# w = 5
# items = [{'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000},
#          {'weight':1, 'value':1000000000}]
#--------- 入力例3 ----------
# w = 15
# items = [{'weight':6, 'value':5},
#          {'weight':5, 'value':6},
#          {'weight':6, 'value':4},
#          {'weight':6, 'value':6},
#          {'weight':3, 'value':5},
#          {'weight':7, 'value':2}]
#----------------------------
n = len(items)    # 品物の総数

# メモ化テーブル（動的計画法用）
memo = {}

for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w + 1):          # 重さ＋1までループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            # 品物を入れない
            memo[i + 1, j] = memo.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = memo.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = memo.get((i, j - items[i]['weight']), 0) + items[i]['value']
            memo[i + 1, j] = max(a, b)    # 価値が高いほうを選択

print('【メモ化テーブルの内容】')
for i, item in enumerate(items):    # 品物ごとにループ
    for j in range(w):              # 重さごとにループ
        print(str(memo[i+1, j+1]).rjust(2, ' '), end=' ')
    print()
print('-----------------------')
print('解（価値の総和の最大値）：', memo[len(items), w])

#--------- 入力例1 ----------
lst = [(10, 40, 70),
       (20, 50, 80),
       (30, 60, 90)]
#--------- 入力例2 ----------
# lst = [(100, 10, 1)]
#--------- 入力例3 ----------
# lst = [(6, 7, 8),
#        (8, 8, 3),
#        (2, 5, 2),
#        (7, 8, 6),
#        (4, 6, 8),
#        (2, 3, 4),
#        (7, 5, 1)]
#----------------------------
n = len(lst)    # 夏休みの日数
# メモ化テーブル（動的計画法用の2次元配列。第１引数：夏休みの日数＋１日、第２引数：３つの活動）
memo = [[0 for i in range(3)] for j in range(n + 1)]

for i in range(n):          # 夏休みの日数分ループ
    for j in range(3):      # 前日の活動 
        for k in range(3):  # 当日の活動
            if j == k:      # 前日と同じ活動はできない
                continue
            # i-1日目(前日)にjの活動、i日目にkの活動を行う場合の幸福度
            memo1 = memo[i][j] + lst[i][k]
            # memo[i + 1][k]はi日目にkを行ったときの得られる累積の最大幸福度
            memo[i + 1][k] = max(memo[i + 1][k], memo1)

for i in range(n + 1):
    print(f'{i}日目の累積最大幸福度', memo[i])
print('解（幸福度の総和の最大値）：',max(memo[n]))

#---------- 入力例 ----------
s = 'erasedream'
#----------------------------
n = len(s)      # 文字列の長さ
memo = [False] * (n + 1)    # メモ化テーブル（動的計画法用の配列）
memo[0] = True

# memo[0]、memo[1]、…、memo[n]を順に求める
for i in range(n + 1):
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'erase':
        print(i, 'erase')
        memo[i] = True
    if i >= 6 and memo[i - 6] and s[i - 6:i] == 'eraser':
        print(i, 'eraser')
        memo[i] = True
    if i >= 5 and memo[i - 5] and s[i - 5:i] == 'dream':
        print(i, 'dream')
        memo[i] = True
    if i >= 7 and memo[i - 7] and s[i - 7:i] == 'dreamer':
        print(i, 'dreamer')
        memo[i] = True
print('memo', memo)
print('解：Yes' if memo[n] else '解：No')

#--------- 入力例1 ----------
k=3
lst = [10, 30, 40, 50, 20]
#--------- 入力例2 ----------
# k=1
# lst = [10, 20, 10]
#--------- 入力例4 ----------
# k=100
# lst = [10, 10]
#--------- 入力例4 ----------
# k=4
# lst = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
#----------------------------
n = len(lst)      # 段差の数

memo = [float('inf')] * n

memo[0] = 0
for i in range(n):
    for x in range(1, k + 1):
        if i - x >= 0:
            memo[i] = min(memo[i], memo[i - x] + abs(lst[i] - lst[i - x]))
print(memo[n-1])

#--------- 入力例1 ----------
lst = [10, 30, 40, 20]
#--------- 入力例2 ----------
# lst = [10, 10]
#--------- 入力例3 ----------
# lst = [30, 10, 60, 10, 60, 50]
#----------------------------
n = len(lst)    # 足場の数

memo = [float('inf')] * n
memo[0] = 0

for i in range(n):
    if i - 1 >= 0:
        memo[i] = min(memo[i], memo[i - 1] + abs(lst[i] - lst[i - 1]))
    if i - 2 >= 0:
        memo[i] = min(memo[i], memo[i - 2] + abs(lst[i] - lst[i - 2]))
print(memo[n - 1])

#---------- 入力例 ----------
a = 'ABCBDAB'
b = 'BDCABA'
#----------------------------
# メモ化テーブル
memo = {}

for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        if a1 == b1:    # 文字が一致した場合
            # 最長共通部分列の長さを１つ増やす
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:           # 文字が一致しない場合
            # これまでの最長共通部分列で長いほうを選択
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))

print('解：', memo[(len(a), len(b))])

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# 動的配列
dp = {}
for i in range(0, len(items) ):             # アイテムを順方向にループ
    for j in range(capacity + 1):           # 重さを順番にループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i + 1, j] = dp.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i, j - items[i]['weight']), 0) + items[i]['value']
            dp[i + 1, j] = max(a, b)        # 価値が高いほうを選択

print('解：', dp[len(items), 5])

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化テーブル
dp = {}
for i in range(len(items) - 1, -1, -1):     # アイテムを後ろからループ
    for j in range(capacity + 1):
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i, j] = dp.get((i + 1, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i + 1, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i + 1, j - items[i]['weight']), 0) + items[i]['value']
            dp[i, j] = max(a, b)    # 価値が高いほうを選択

print('解：', dp[0, 5])