POJ 1952 BUY LOW, BUY LOWER DP記錄數據
最長遞減子序列,加記錄有多少個最長遞減子序列,然後需要去重。
最麻煩的就是去重了。
基本的思路就是:全面出現重復的值,然後還是相同長度的子序列,這裡的DP記錄的子序列是以當前值為結尾的時候,並且一定選擇這個值的最長遞減子序列, 那麼就需要減去前面已經出現過了的子序列。
有點繞口。
舉例就是9 8 9 8 2 和 10 5 12 5 3;這些例子去重。
本類型的題目如果不用記錄數據是可以使用O(nlgn)的算法的,不過暫時不知道如何記錄數據。故此這裡只使用DP了。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include