借杭电这道题总结一下最长上升子序列（LIS）问题，最长上升子序列有o(n^2)和o(nlogn)两种算法（Matrix67那还有一种o(nm)的算法，不过没看懂）。
o(n^2)算法不用多说，就是依次遍历整个序列，每一次求出从第一个数到当前这个数的最长上升子序列，直至遍历到最后一个数字为止，然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度，那么dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。
LIS函数代码如下：
// Author: Tanky Woo
// Blog: www.WuTianQi.com
int dp[1000];
int LIS(int arr[1000], int n)
{
for(int i=1; i<=n; ++i)
dp[i] = 0;
int ans;
dp[1] = 1;
for(int i=2; i<=n; ++i)
{
ans = dp[i];
for(int j=1; j<i; ++j)
{
if(arr[i]>arr[j] && dp[j]>ans)
ans = dp[j];
}
dp[i] = ans+1;
}
ans = 0;
for(int i=1; i<=n; ++i)
{
if(dp[i] > ans)
ans = dp[i];
}
return ans;
}
另为一种o(nlogn)算法，这种算法的操作如下：
开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。最长序列长度即为栈的大小top。
这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。
举例：原序列为1，5，8，3，6，7
栈为1，5，8，此时读到3，用3替换5，得到1，3，8；再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。
这道题显然是用第二种算法（1 <= N <= 50W），代码如下：
#include <stdio.h>
#define N 500005
int num[N], dp[N];
int find(int low, int high, int i) //二分法查找 确定num[i]的位置
{
while(low <= high)
{
int mid = (low+high)/2;
if(i > dp[mid]) low = mid + 1;
else high = mid - 1;
}
return low; //返回其位置
}
int main()
{
int n, a, b, i, len, Case = 0, low;
//freopen("data.in", "r", stdin);
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i++)
{
scanf("%d%d", &a,&b);
num[a] = b;
}
dp[1] = num[1];
len = 1;
for(i = 2; i <= n; i++)
{
low = find(1, len, num[i]); //确定num[i]的位置，
dp[low] = num[i]; //如果num[i]比dp[]里的所有元素都大，则将num[i]存入dp[],否则替换掉dp[]序列里第一个比num[i]小的数
if(low > len) len++; //如果low>len说明将num[i]存入了dp[]，所求LIS的长度加1；
}
if(len == 1) printf("Case %d:\nMy king, at most %d road can be built.\n\n", ++Case, len);
else printf("Case %d:\nMy king, at most %d roads can be built.\n\n", ++Case, len);
}
return 0;
}