主題

ZeroJudge - a522: 12455 - Bars 解題心得

Not In My Back Yard | 2021-01-14 00:00:01 | 巴幣 0 | 人氣 37

題目連結:


題目大意:
輸入第一列給定一正整數 t (t ≦ 50),代表有 t 筆測試資料。每筆測資第一列給定一整數 n (0 ≦ n ≦ 1000),代表要求的目標金屬棒之長度。接著第二列給定一正整數 p (1 ≦ p ≦ 20),代表有 p 根金屬棒。接著一列給定 p 個正整數,代表 p 根金屬棒各自的長度。

金屬棒不能切割,但是可以彼此焊接成更長的金屬棒。試問這 p 根金屬棒可不可以接成目標長度 n 的金屬棒?



範例輸入:
4
25
4
10 12 5 7
925
10
45 15 120 500 235 58 6 12 175 70
120
5
25 25 25 25 25
0
2
13 567


範例輸出:
NO
YES
NO
YES


解題思維:
這題為典型的子集合加總問題(Subset Sum Problem),可以視為換硬幣題目之變體,像是這題也是類似的變體。只是這次不是要求盡量靠近 n 值,是直接問能不能湊到 n 。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作