1175: 金明的预算方案(python代码）

解题思路:

注意事项:

参考代码:

p,n=map(int,input().split())
lis=[]
l=[]
p//=10
for i in range(n):
    a,b,c=map(int,input().split())
    a//=10
    if c==0:
        lis.append([a,a*b])
    else:
        l.append([a,a*b,c])
lt=[[] for i in range(len(lis))]
for i in l:
    lt[i[2]-1].append(i)
ls=[[i] for i in lis]
for i in range(len(lis)):
    if len(lt[i])==1:
        s=[lt[i][0][j]+ls[i][0][j] for j in range(2)]
        ls[i].append(s)
    if len(lt[i])==2:
        s=[lt[i][0][j]+ls[i][0][j] for j in range(2)]
        ls[i].append(s)
        s=[lt[i][1][j]+ls[i][0][j] for j in range(2)]
        ls[i].append(s)
        s=[lt[i][1][j]+ls[i][0][j]+lt[i][0][j] for j in range(2)]
        ls[i].append(s)
li=[]
for i in ls:
    li.append(len(i))
dp=[0 for i in range(p+1)]
for num in range(len(ls)):
    for pri in range(p,-1,-1):
        for i in range(li[num]):
            if pri >= ls[num][i][0]:
                dp[pri]=max(dp[pri],ls[num][i][1]+dp[pri-ls[num][i][0]])
        
print(dp[-1]*10)