声明

发现题解区居然没有python解法

又发现讨论区大佬@[roon2300]有很好的python解法

于是稍加注释以及排版，将大佬的题解贴出来，以供大家参考

N=20001
class node:
    def __init__(self, pos, val):
        self.pos=pos
        self.val=val

dp=[0]*N

q=[node(0,0) for i in range(N)]

[n,m]=map(int,input().split())

while n:

    [v,w,s]= map(int,input().split())

    for j in range(v):

        hh=0
        #区间首端
        tt=0
        #区间尾端
        stop=(m-j)//v
        #区间长度
        for k in range(0,stop+1):

            val=dp[k*v+j]-k*w

            while hh<tt and val>=q[tt-1].val:
            #维护单调性
                tt-=1

            q[tt].pos=k

            q[tt].val=val

            tt+=1
            #延长区间

            if q[hh].pos<k-s:
            #数量限制
                hh+=1

            dp[v*k+j]=q[hh].val+k*w
            #还原
    n-=1

print(dp[m])