如何找到上行子

Question

我遇到一個問題的最低數量。 http://poj.org/problem?id=1065
的問題是要找到上升的子序列的最小數量。
我看到有人是要找到最長下降子序列的長度。 我不知道爲什麼這兩個數字是平等的。

#include <iostream> 
#include <algorithm> 
#include <functional> 
#include <memory.h> 
/* run this program using the console pauser or add your own getch, 
system("pause") or input loop */ 
using namespace std; 
pair<int,int> stick[5000]; 
int dp[5000]; 

int main(int argc, char** argv) { 
int t; 
cin>>t; 
while(t--){ 
    int n; 
    cin>>n; 
    for(int i=0;i<n;i++){ 
     cin>>stick[i].first>>stick[i].second; 
     } 
    sort(stick,stick+n); 
    memset(dp,-1,sizeof(int)*5000); 
    for(int i=0;i<n;i++){ 
     *lower_bound(dp,dp+n,stick[i].second,greater<int>())=stick[i].second; 
     } 
     cout<<lower_bound(dp, dp + n, -1, greater<int>()) - dp<<endl; 

    } 
return 0; 
} 

Answer 1

它立即從Dilworth's theorem。這是解決這類問題的標準技術。