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

 

DP題,求LIS

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

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

 

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

然後從後面求LIS

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