fork download
  1. import sys
  2.  
  3. def solve():
  4. # 入力データの読み込み
  5. input_data = sys.stdin.read().split()
  6. if not input_data:
  7. return
  8.  
  9. n = int(input_data[0])
  10. jobs = []
  11. idx = 1
  12. for i in range(n):
  13. s = int(input_data[idx])
  14. t = int(input_data[idx+1])
  15. v = int(input_data[idx+2])
  16. jobs.append({'s': s, 't': t, 'v': v})
  17. idx += 3
  18.  
  19. # 1. 終了時刻 t で安定ソートを行う
  20. # Pythonの sort() は安定ソートです
  21. jobs.sort(key=lambda x: x['t'])
  22.  
  23. # 1-indexedで管理するため、先頭にダミーを追加
  24. sorted_jobs = [{'s': 0, 't': 0, 'v': 0}] + jobs
  25.  
  26. # 2. p(j) の計算
  27. p = [0] * (n + 1)
  28. for j in range(1, n + 1):
  29. for i in range(j - 1, 0, -1):
  30. if sorted_jobs[i]['t'] <= sorted_jobs[j]['s']:
  31. p[j] = i
  32. break
  33.  
  34. # 3. 動的計画法 (DP) で各段階の最適値を計算
  35. opt = [0] * (n + 1)
  36. for j in range(1, n + 1):
  37. # 漸化式: OPT(j) = max(v_j + OPT(p(j)), OPT(j-1))
  38. val_include = sorted_jobs[j]['v'] + opt[p[j]]
  39. val_exclude = opt[j-1]
  40.  
  41. if val_include >= val_exclude:
  42. opt[j] = val_include
  43. else:
  44. opt[j] = val_exclude
  45.  
  46. # 4. 最適解(ジョブの集合)を求める
  47. # スライドのアルゴリズムに従い、後ろから遡る
  48. solution = []
  49. curr = n
  50. while curr > 0:
  51. # 「そのジョブを選んだ場合」の値が、現在のOPT値と等しいかチェック
  52. # 同点の場合は現在のジョブを選ぶ(条件: >= )
  53. if sorted_jobs[curr]['v'] + opt[p[curr]] >= opt[curr-1]:
  54. solution.append(curr)
  55. curr = p[curr] # 直前の非競合ジョブへジャンプ
  56. else:
  57. curr -= 1 # 一つ前のジョブへ移動
  58.  
  59. # 出力例1, 2, 3 の形式に合わせてリストをそのまま出力
  60. print(solution)
  61.  
  62. if __name__ == "__main__":
  63. solve()
Success #stdin #stdout 0.13s 14120KB
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]