※ 引述《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