Wie finde ich die minimale Anzahl der aufsteigenden Untersequenz

Question

Ich triff ein Problem. http://poj.org/problem?id=1065
Das Problem besteht darin, die minimale Anzahl aufsteigender Subsequenzen zu finden.
Ich sehe jemand ist die Länge der längsten absteigenden Teilfolgen zu finden. Ich weiß nicht, warum die zwei Zahlen gleich sind.

#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

Es folgt sofort aus der Dilworth's theorem. Es ist eine Standardtechnik, um solche Probleme zu lösen.