最长上升子序列。
怎么做呢?
不知道。
书上说用dp。
这样做的,
dp[i]:长度为i的递增子序列,末尾元素最小的值。
也就是说对于一个数列a,
可以得到如下状态转移方程:
dp[i]=a[j]>dp[i-1]?min(a[j],dp[i]):dp[i].
这样的话容易得到如下代码:
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int inf,i,j,dp[1010],arr[1010],num; scanf("%d",&num); for(i=0;i<num;i++) scanf("%d",&arr[i]); memset(dp,127,sizeof(dp)); inf=dp[0]; for(i=0;i<num;i++) for(j=0;j<num;j++) if(j==0||dp[j-1]<arr[i]) dp[j]=min(arr[i],dp[j]); for(i=num-1;dp[i]==inf;i--); cout<<i+1<<endl; }
可以看出dp数组一定是个递增数列,
于是用二分查找优化下,
得到如下代码:
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int main() { int inf,i,j,dp[1010],arr[1010],num; scanf("%d",&num); for(i=0;i<num;i++) scanf("%d",&arr[i]); memset(dp,127,sizeof(dp)); inf=dp[0]; for(i=0;i<num;i++) *lower_bound(dp,dp+num,arr[i])=arr[i]; cout<<lower_bound(dp,dp+num,inf)-dp; }
lower_bound会利用二分查找,在dp数组中找到一个大于或等于arr[i]
的最小指针。