Competitive Programing Typical 90 Problem day11

Day 11.

This problem is interesting because its idea is really useful in our daily lives.

When applying its idea, what matters most is how to calculate score of each task and how to estimate the time we will spend on it. 

 

Code is below.

N = int(input())
DCS = []
for i in range(N):
  d,c,s = map(int,input().split())
dcs = (d,c,s)
  DCS.append(dcs)

sort_d = lambda value :value[0]
DCS.sort(key = sort_d)

dp = [[0]*5001 for i in range(N+1)]
for i in range(N):
  d_now, c_now, s_now = DCS[i]
  for j in range(5001):
    if c_now <= j <= d_now:
      dp[i+1][j] = max(dp[i][j-c_now]+s_now, dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]

answer = max(dp[N])
print(answer)
  • As shown in the public answer, best strategy is sorting by the deadline, and to take or throw away each task from earlier ones.
    • the deadline d1 <= d2 <= d3 <= ,... <= di
    • if "" c1 + c2 + ... + ci <= di (i = 0, 1, ..., n) "" , we can complete all tasks. 
    • this is necessity and sufficiency. ]
      • about necessity and sufficiency, here is refference.
  • Another important thing is sorting by some order, and do DP.
    • as is often the case with competitive programing, each array has some order.
    • it maybe useful to sort elements by some intrinsic order
      • the order is forward or backward.
    • after sorting, dynamic programing start.

Bye bye!