Submit Ranklist
Problem : 38 - 職棒簽約問題
Problem Statistics
Solved Member:
36 Submission:
86 User Tried:
36 Statement:
職棒打假球事件重創了我國的職業棒球運動，有許多球星因為涉案而遭球團開除退出職棒，這也使許多球隊面臨了球員不足的窘境。因此在這段時間各球團都很積極地在自由球員市場物色適當的球員來補足戰力的缺口，而且各球團的總經理都正為同一個問題煩惱，即如何在有限的經費下與適合的球員簽約，使球隊的戰力獲得最大的提昇。
更具體的來說，假設標哥是某職棒球隊的總經理，他有M(<= 10000)單位的預算可以用來與球員簽約，且他的球隊有N個位置需要引進球員補強，為了簡化問題假設每個位置都有P位自由球員可供選擇，這N個位置可以是有關打擊、手備或投手等位置的補強，每位自由球員只專注於一個位置，故總共會有NP位自由球員可供考慮，每個位置最多只補一位自由球員，因為該位置可能已有球員負責。此外每位球員有三項資訊可供標哥參考並決定是否與該球員簽約，即該球員(1)負責的位置、(2)簽約金額(<=10000)、(3)戰力指數(<=100)。戰力指數是一非負整數用來衡量一球員的能力，戰力指數愈大表示能力愈強。給定球隊的預算及須要補強的位置數以及所有相關球員的資訊，你的任務是寫一個程式幫標哥計算如何在預算內簽下自由球員以補充戰力並且使所簽下的球員戰力指數總和最大。
Input:Output:
第一行輸入三個正整數M(<= 10000)、N(<= 50)及P(<=50)分別代表標哥的預算、所須補強的位置數以及每個位置的人選個數。接下來的N行中，每一行則輸入2P個大於等於0的整數，其中第I行用來代表可以勝任第I個位置的球員資訊，兩個數字一組分別用來描述一位球員的簽約金及戰力指數，數字間以一或多個空白區隔。
輸出一數字顯示標哥所能簽到的最大戰力指數總和。
Sample Input:Sample Output:
SAMPLE 1:
10000 2 3
5000 2 10000 5 5000 1
5000 6 10000 5 5000 5
SAMPLE 2:
10000 3 3
1000 2 1000 3 10000 5
10000 3 5000 6 3000 5
1000 7 2000 5 2000 6
SAMPLE 1:
8
SAMPLE 2:
16
Source:
TOI 2010
Problem Setter
Nekosyndrome Testdata:
| Test | Time | Memory | Score |
|---|
| 0-1 | 1000ms | 65536kb | |
| 0-2 | 1000ms | 65536kb | |
| 1 | 1000ms | 65536kb | 20 |
| 2 | 1000ms | 65536kb | 20 |
| 3 | 1000ms | 65536kb | 20 |
| 4 | 1000ms | 65536kb | 20 |
| 5 | 1000ms | 65536kb | 20 |