[理工] [algo] 99中央 第5題

[aoqq12 (阿任)]

http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_99_01.pdf


今天一直卡住= =  第五題


感覺上用dp能做出來   可是想半天  還是卡住


我是想說先將 x y z排序

然後 a[i]= k-xi

在到 y or z排序好的 找小於a[i]的數來做組合


不過好像很沒技術性....= ="


這該怎麼解= =" 才會比較有效率   有請高手解惑 orz



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.105.255.144
※ 編輯: aoqq12          來自: 112.105.255.144      (01/08 22:54)
※ 編輯: aoqq12          來自: 112.105.255.144      (01/08 22:55)
推 christianSK:這題是ACM來的, 關鍵點在於sort可以降低複雜度
推 christianSK:還有 x + y = k - z
→ aoqq12:所以我在稍微修改一下 關鍵運算就好的意思嘛@@
推 christianSK:關鍵運算是指?
→ aoqq12:就類似你說的x+y=k-z啊!!
→ aoqq12:這樣想是對的嘛= =a?
推 christianSK:其實我不太懂你的意思XD"
→ aoqq12:XD
推 LinkCar:用DP應該是O(k)  k過大會有問題  不適合拿來做答案
→ LinkCar:     更正 O(X+Yk+Zk)
→ sneak: 其實我不太懂你的意思X https://daxiv.com