농부 영호의 N(1≤N≤500)마리의 소들은 세계적으로 유명한 Multistate Milking Match-up(MMM) 대회에 참가할 우유생산 팀을 선발하려고 한다. 아마 당신도 알고 있듯이 최소한 X(1≤X≤1,000,000) 갤런의 우유를 생산한 어떤 팀도 승자가 된다.

각각의 소는 -10,000 부터 10,000 갤런 사이의 기여를 할 수 있는 잠재력을 가지고 있다. (슬프게도 몇몇의 소들은 다른 소들이 생산한 우유가 담긴 우유병을 엎어버리기도 한다.)

MMM 대회는 가족의 가치를 촉진 시킨다는데 스스로를 자랑스러워 한다. 농부 영호의 소들은 X 갤런의 우유를 생산해서 승자가 될 것에는 전혀 의심치 않는다. 하지만 대회의 정신을 지지하기 위해 그들은 가능한 많은 부모-자식 관계들을 포함한 팀을 출전시키려고 한다(여전히 최소 X갤런의 우유를 생산하면서). 놀랄것도 없이 농부 영호의 모든 소들은 암컷이다.

농부 영호의 소들의 가족 계보도와 각각의 소들이 우유 생산에 기여하는 양이 주어졌을 때 영호가 선택할 수 있는 승자 팀중에 가능한 부모-자식 관계의 수의 최대값을 계산하라. 할머니-어머니-딸 조합의 소들 집합은 두 개의 부모-자식 관계가 있다(할머니-어머니 어머니-딸).

#1032 upload 46회 done 13회 how_to_reg 5명

우유생산팀 선발 timer 1초 memory 32MB

#1032

우유생산팀 선발 1초 32MB