fork download
  1. # 重み付き区間スケジューリング(最適解のジョブ集合)
  2.  
  3. n = int(input())
  4.  
  5. jobs = []
  6. for i in range(1, n + 1):
  7. s, f, v = map(int, input().split())
  8. jobs.append((i, s, f, v)) # (元の番号, 開始, 終了, 価値)
  9.  
  10. # 終了時刻で安定ソート
  11. jobs.sort(key=lambda x: x[2])
  12.  
  13. # q(i) の計算
  14. q = [0] * (n + 1)
  15. for i in range(1, n + 1):
  16. si = jobs[i - 1][1]
  17. qi = 0
  18. for j in range(i - 1, 0, -1):
  19. if jobs[j - 1][2] <= si:
  20. qi = j
  21. break
  22. q[i] = qi
  23.  
  24. # OPT の計算
  25. OPT = [0] * (n + 1)
  26. for i in range(1, n + 1):
  27. v = jobs[i - 1][3]
  28. OPT[i] = max(OPT[i - 1], OPT[q[i]] + v)
  29.  
  30. # 最適解の復元
  31. result = []
  32. i = n
  33. while i > 0:
  34. v = jobs[i - 1][3]
  35. if OPT[i] == OPT[q[i]] + v:
  36. result.append(jobs[i - 1][0]) # 元のジョブ番号
  37. i = q[i]
  38. else:
  39. i -= 1
  40.  
  41. # 出力(降順のまま)
  42. print(result)
  43.  
Success #stdin #stdout 0.1s 14032KB
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
[8, 2, 4]