內容
已知有 n 個寶盒編號 0 到 n−1 以及 m 種鑰匙編號 0 到 m−1。一開始你有 t 種鑰匙分別為 x1,⋯,xt。
每一個寶盒要打開都需要同時擁有k 種鑰匙，第 i 個寶盒分別需要 ri1,ri2,⋯,rik 種類的鑰匙。每個寶盒打開後都會得到 k 種鑰匙，第 i 個寶盒打開後分別會得到 si1,si2,⋯,sik 種類的鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過 60。
請輸出最多可以開啟多少個寶盒。
子問題一 (20%) k=1, 1≤n,m≤100
子問題二 (20%) k=1, 1≤n,m≤105
子問題三 (60%) 1≤k≤5, 1<=n,m<=105
輸入說明
第一行輸入三個正整數 n,m,k(1≤n,m≤105,1≤k≤5) 代表有 n 個寶盒，m 種鑰匙以及每個寶盒需要的鑰匙數量 k。
接下來輸入一行，第一個數字 t 代表一開始有的鑰匙種類數量，後面有 t 個數字代表這些鑰匙分別的種類。
接下來有 n 行，每一行有 k 個數字，代表要開啟第i 個寶盒的第 j 種鑰匙為rij。
最後有 n 行，每一行有 k 個數字，代表開啟第 i 個寶盒後得到的第 j 種鑰匙為 sij。
輸出說明
輸出一個正整數，代表可以開啟的寶盒數量。
範例輸入
#1
5 5 1 2 0 1 0 2 4 3 1 1 2 4 3 3
範例輸出
#1
3
範例輸入
#2
10 8 2 3 6 5 2 5 6 2 7 2 0 4 5 5 1 3 0 4 2 2 4 5 3 5 6 5 0 0 6 1 7 3 2 2 1 7 3 4 7 4 5 4 1 7 5
範例輸出
#2
5
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 ：
標籤:
出處:
2023年6月APCS
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||