题目链接：kuanbin带你飞基础dp专题:hdu1257
这是一道经典的LIS题目。一句话可以概括这道题目的变形：最长上身子序列的长度等于不下降子序列的个数。然后用dp做的时间复杂度是O(n),可以用二分优化，时间复杂度为O(nlogn)。
ac代码:
#include <bits/stdc++.h>
using namespace std;
int a[1000000], dp[1000000];
int main(void)
{
int N;
while(scanf("%d", &N)!=EOF)
{
memset(dp, 0, sizeof(dp));
dp[0]=1;
for(int i=0; i<N; i++)
scanf("%d", &a[i]);
for(int i=0; i<N; i++)
{
for(int j=0; j<i; j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i], dp[j]+1);
}
if(dp[i]==0)dp[i]=1;
}
int M=-1;
for(int i=0; i<N; i++)M=max(M, dp[i]);
printf("%d\n", M);
}
return 0;
}
