Re: [問題] 請問一個問題
※ 引述《vcore (vcore)》之銘言：
: 請各位大大幫忙~
: 問題如下:
: 有一個矩陣 4*4矩陣
: 例如
: 15 0 0 5
: 0 50 20 30
: 35 5 0 15
: 0 65 50 70
: 請求出最少線段覆蓋 全部的"0"
: ( 線段是以覆蓋整個row或整個col )
: 例如
: 15-0-35-0 這條線段覆蓋了2個0
: 15-0-0-5 覆蓋2個0
: 35-5-0-15 覆蓋一個0
: 所以上面這個例子 最少要用3個線段覆蓋全部的0
: 給定N*N矩陣
: 求出最少需幾條線段覆蓋全部的"0"
: N <= 100
: 請問各位這題要用什麼演算法?
: 謝謝!
印象中這題隨機客老師好像在前年的IOI營中有提出來過....
(只是改成修理電路板的型式)
記得當時老師說這個題目是NPC?
當然前年的事要記錯也是很容易的 所以如果有錯還請指正 Orz
--
"LPH" is for "Let Program Heal us"....
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.54
討論串 (同標題文章)