HDU 1025は、高効率で最長の上昇サブシーケンス(サブチェック)を有する.

LIS(Longest Increase Subsequence)の最長上昇(下降しない)サブシーケンスを用いて、2つのアルゴリズムの複雑度はO(n＊logn)とO(n＾2)である.前者は二分検索で、後者は地味検索です.そのアルゴリズムの大まかな考え:2つのa,b配列を設定し、a配列はデータを格納し、b配列は最長の降順シーケンスを記憶する.このアルゴリズムの鍵は二分割検索を設計することです.
最初はシンプルなdpアルゴリズムを使いましたが、果敢にタイムアウトしました.タイムアウトコードは以下の通りです.

 #include <iostream>
#include <algorithm>
using namespace std;
const int Max = 500010;
int dp[Max];
typedef struct 
{
    int x, y;
} Node;
Node node[Max];

int cmp(const void * a, const void * b)
{
    return (*(Node*)a).x - (*(Node*)b).x;
}
int main()
{
    int n;
    int t = 1;
    while(cin >> n)
    {
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++)
            scanf("%d%d", &node[i].x, &node[i].y);
        //qsort(node, n, sizeof(Node), cmp);
        /*for(int i = 0;  i < n; i++)
            printf("%d %d
", node[i].x, node[i].y);*/
        for(int i = 0; i < n; i++)
        {
            dp[i] = 1;
            for(int j = i - 1; j >= 0; j--)
            {
                if(dp[j] + 1 > dp[i] && node[i].y > node[j].y)
                    dp[i] = dp[j] + 1;
            }
        }
        int max = 0;
        for(int i = 0; i < n; i++)
            if(dp[i] > max)
                max = dp[i];
        printf("Case %d:
", t++);
        printf("My king, at most %d road can be built.

", max);
    }
    return 0;
}

改善後、二分で検索します.ずっとわけがわからなくて、まだ原因が見つかりません.データに問題がありますか?
Waコード:

#include <iostream>
#include <algorithm>
using namespace std;
const int Max = 500010;
int dp[Max];
int B[Max];
typedef struct 
{
	int x, y;
} Node;
Node node[Max];

int cmp(const void * a, const void * b)
{
	return (*(Node*)a).x - (*(Node*)b).x;
}
int main()
{
	freopen("1025.txt", "r", stdin);
	int n;
	int t = 1;
	while(cin >> n)
	{
		memset(dp, 0, sizeof(dp));
		memset(B, 0, sizeof(B));
		for(int i = 0; i < n; i++)
			scanf("%d%d", &node[i].x, &node[i].y);
		qsort(node, n, sizeof(Node), cmp);
		B[0] = -1000;
		B[1] = node[0].y;
		int len = 1;
		int p, r, m;
		for(int i = 1; i < n; i++)
		{
			p = 1; 
			r = len;
			while(p <= r)
			{
				m = (p+r) / 2;
				if(B[m] < node[i].y) 
					p = m + 1;
				else
					r = m - 1;
			}
			B[p] = node[i].y;
			if(p > len) len = p;
		}
		printf("Case %d:
", t++);
		printf("My king, at most %d road can be built.

", len);
	}
	return 0;
}

最後にACコードです.http://www.cnblogs.com/hankers/archive/2012/02/07/2340904.html

#include<stdio.h>
 int dp[50005],a[50005];
 
 int Lis(int n)
 {
     int len=1,i,low,high,mid;
     dp[1]=a[1];
     for(i=2;i<=n;i++)
     {
        low=1;
        high=len;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(a[i]>dp[mid])
                low=mid+1;
            else
                high=mid-1;
        }
        dp[low]=a[i];
        if(low>len)
            len=low;
     }
     return len;
 }
 int main()
 {
     int n,x,y,i,ans,k=1;
     while(scanf("%d",&n)!=EOF)
     {
         for(i=0;i<n;i++)
         {
             scanf("%d%d",&x,&y);
             a[x]=y;
         }
         ans=Lis(n);
         printf("Case %d:
",k++);
         if(ans==1)
             printf("My king, at most 1 road can be built.
");
         else
             printf("My king, at most %d roads can be built.
",ans);
         printf("
");
     }
     return 0;
 }

実は明らかにこの配列は小さいですが、acができます.
日を改めてWaの原因を探し続けます.