昇順サブシーケンスの最小数を見つける方法

Question

問題が発生しました。 http://poj.org/problem?id=1065
問題は、昇順サブシーケンスの最小数を見つけることです。
誰かが最も長い降順サブシーケンスの長さを見つけることがわかります。 2つの数字が等しい理由はわかりません。

#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からすぐに続きます。このような問題を解決するための標準的な手法です。