HDU 1574 - RP Wen Ti
Problem : Some event happens in order. each event has dRP[i], bRP[i], val[i]. If dRP[i]>0, it can be happen when current RP<=bRP[i], and get val[i] values, get dRP[i]'s RP change. If dRP[i]<0, it will happen when current RP>=bRP[i], and will get val[i] values, and get dRP[i]'s RP change. The initial RP is 0, output the maximum value one can get.
Solution : f[i][j] is the i-th event passed, with RP j, the maximum value it can get. Then it becomes a knapsack problem. Note that the input is very large (N=1000 round, M=10000 space), discretization is needed (using SET).