Q: http://uva.onlinejudge.org/external/101/10131.html

 

DP題,求LIS

比較特別的是這題的data不是partially ordered (IQ比較高的大象不一定體重比較重)

所以不能用O(nlogn)的方法,要用O(n^2)的

 

先對大象的體重由小到大作排序,如果體重一樣就讓IQ比較高的在前面

然後從後面求LIS

需注意條件必須是"IQ比較高且體重比較重"才有符合嚴格遞增的條件

 

 

 

arrow
arrow
    文章標籤
    ACM UVA 程式 DP
    全站熱搜
    創作者介紹
    創作者 Tube 的頭像
    Tube

    Tube's World

    Tube 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄