fork download
copy 
  1. import sys
  2.  
  3. # 再帰回数のカウント用グローバル変数
  4. call_count = 0
  5.  
  6. class Job:
  7.     def __init__(self, start, end, weight):
  8.         self.start = start
  9.         self.end = end
  10.         self.weight = weight
  11.  
  12. def solve():
  13.     # 入力の読み込み
  14.     try:
  15.         line1 = sys.stdin.readline()
  16.         if not line1: return
  17.         n = int(line1.strip())
  18.     except EOFError:
  19.         return
  20.  
  21.     jobs = []
  22.     for _ in range(n):
  23.         s, e, w = map(int, sys.stdin.readline().split())
  24.         jobs.append(Job(s, e, w))
  25.  
  26.     # 1. 終了時刻でソート (これがアルゴリズムの前提)
  27.     jobs.sort(key=lambda x: x.end)
  28.  
  29.     # 2. p(j) の計算: ジョブjと衝突しない、直前のジョブのインデックス
  30.     # p[j] は jobs[j-1] と両立する最大のインデックス (1-indexed)
  31.     p = [0] * (n + 1)
  32.     for j in range(1, n + 1):
  33.         for i in range(j - 1, 0, -1):
  34.             if jobs[i-1].end <= jobs[j-1].start:
  35.                 p[j] = i
  36.                 break
  37.  
  38.     # --- 通常の再帰 ---
  39.     global call_count
  40.     call_count = 0
  41.  
  42.     def compute_opt(j):
  43.         global call_count
  44.         call_count += 1
  45.         if j == 0:
  46.             return 0
  47.         # 課題の指示通り OPT(n-1) を先に呼び出し、次に OPT(p(n)) を呼び出す
  48.         res_exclude = compute_opt(j - 1)
  49.         res_include = jobs[j-1].weight + compute_opt(p[j])
  50.         return max(res_exclude, res_include)
  51.  
  52.     ans_rec = compute_opt(n)
  53.     print(f"opt: {ans_rec}")
  54.     print(f"calls: {call_count}")
  55.  
  56.     # --- メモ化再帰 ---
  57.     call_count = 0
  58.     memo = [-1] * (n + 1)
  59.  
  60.     def m_compute_opt(j):
  61.         global call_count
  62.         call_count += 1
  63.         if j == 0:
  64.             return 0
  65.         if memo[j] != -1:
  66.             return memo[j]
  67.  
  68.         # 指示通り OPT(j-1) -> OPT(p(j)) の順で評価
  69.         res_exclude = m_compute_opt(j - 1)
  70.         res_include = jobs[j-1].weight + m_compute_opt(p[j])
  71.  
  72.         memo[j] = max(res_exclude, res_include)
  73.         return memo[j]
  74.  
  75.     ans_memo = m_compute_opt(n)
  76.     print(f"opt: {ans_memo}")
  77.     print(f"calls: {call_count}")
  78.  
  79. if __name__ == "__main__":
  80.     solve()
Success #stdin #stdout 0.08s 14008KB
comments (?)
stdin
copy 
7
5 9 3
1 3 2
6 11 15
3 4 10
2 4 5
12 15 8
0 14 7
stdout
copy 
opt: 35
calls: 61
opt: 35
calls: 15
https://ideone.com/JGm7th
language:
Python 3 (python  3.12)
created:
11 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!