fork download
  1. import sys
  2.  
  3. def solve():
  4. # 標準入力から全てのデータを読み込み
  5. input_tokens = sys.stdin.read().split()
  6. if not input_tokens:
  7. return
  8.  
  9. n = int(input_tokens[0])
  10.  
  11. # ジョブ情報をリストに格納 [開始時刻, 終了時刻, 価値]
  12. jobs = []
  13. idx = 1
  14. for _ in range(n):
  15. s = int(input_tokens[idx])
  16. f = int(input_tokens[idx + 1])
  17. v = int(input_tokens[idx + 2])
  18. jobs.append([s, f, v])
  19. idx += 3
  20.  
  21. # 1. 終了時刻で安定ソートを実行
  22. jobs.sort(key=lambda x: x[1])
  23.  
  24. # 添字を1から扱うため、先頭にダミー要素を追加
  25. sorted_jobs = [[-1, -1, 0]] + jobs
  26.  
  27. # 2. q(j) の計算
  28. q = [0] * (n + 1)
  29. for j in range(1, n + 1):
  30. sj = sorted_jobs[j][0]
  31. for i in range(j - 1, 0, -1):
  32. if sorted_jobs[i][1] <= sj:
  33. q[j] = i
  34. break
  35.  
  36. # 3. OPT_j の計算 (動的計画法)
  37. opt = [0] * (n + 1)
  38. for j in range(1, n + 1):
  39. vj = sorted_jobs[j][2]
  40. # 漸化式: OPT_j = max(v_j + OPT_{q(j)}, OPT_{j-1})
  41. include_j = vj + opt[q[j]]
  42. exclude_j = opt[j - 1]
  43.  
  44. if include_j >= exclude_j: # 等しい場合はジョブを含める挙動に合わせる
  45. opt[j] = include_j
  46. else:
  47. opt[j] = exclude_j
  48.  
  49. # 4. 最適解(ジョブの集合)の計算(バックトラッキング)
  50. solution = []
  51. curr = n
  52. while curr > 0:
  53. vj = sorted_jobs[curr][2]
  54. # ジョブcurrを含めた場合の価値が、含めない場合(OPT_{curr-1})以上であれば採用
  55. if vj + opt[q[curr]] >= opt[curr - 1]:
  56. solution.append(curr)
  57. curr = q[curr] # 重ならない直近のジョブへ移動
  58. else:
  59. curr -= 1 # ひとつ前のジョブを確認
  60.  
  61. # 指定された形式(降順リスト)で出力
  62. print(solution)
  63.  
  64. if __name__ == "__main__":
  65. solve()
Success #stdin #stdout 0.1s 14020KB
stdin
10
3 9 2
5 6 3
1 10 4
4 5 3
6 13 5
4 8 5
3 19 8
6 16 6
9 11 4
3 8 6
stdout
[9, 2, 1]