POJ2533裸的LIS，时间复杂度为O(n^2)
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=+;
int a[MAXN];
int dp[MAXN];
int n,ans; int main()
{
scanf("%d",&n);
for (int i=;i<n;i++)
{
scanf("%d",&a[i]);
dp[i]=;
}
ans=-;
for (int i=;i<n;i++)
{
for (int j=;j<i;j++)
if (a[j]<a[i] && dp[j]+>dp[i])
{
dp[i]=dp[j]+;
}
if (dp[i]>ans)
{
ans=dp[i];
}
}
cout<<ans<<endl;
return ;
}
POJ1631
两条线路i与j不交叉的前提条件是a[i]<a[j]，即上升子序列。用二分搜索+LIS，时间复杂度为O(n^2)，具体解释详见《挑战程序设计竞赛2.3记录结果在利用的“动态规划”》P65
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=+;
const int INF=+;
int a[MAXN];
int dp[MAXN];//dp[i]表示长度为i+1的上升子序列末位元素的最小值
int n,m,ans,l,r; int search(int k)
{
int ul=l,ur=r;
while (ur-ul>)
{
int mid=(ur+ul)/;
if (dp[mid]>=k) ur=mid;
else ul=mid;
}
return ur;
} int main()
{
scanf("%d",&m);
for (int kase=;kase<m;kase++)
{
scanf("%d",&n);
for (int i=;i<n;i++)
{
scanf("%d",&a[i]);
dp[i]=INF;
}
l=-;
r=;
for (int i=;i<n;i++)
{
int pos=search(a[i]);
dp[pos]=a[i];
if (pos==r) r++;
}
cout<<r<<endl;
}
return ;
}