comment trouver le nombre minimum de sous-séquence ascendante

Question

Je rencontre un problème. http://poj.org/problem?id=1065
Le problème est de trouver le nombre minimum de sous-séquences ascendantes.
Je vois que quelqu'un doit trouver la longueur des plus longues sous-séquences descendantes. Je ne sais pas pourquoi les deux nombres sont égaux.

#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

Il résulte immédiatement du Dilworth's theorem. C'est une technique standard pour résoudre des problèmes comme celui-ci.