洛谷 p1020 题解 求最长上升子序列的o(n*logn)算法
题目链接:
https://www.luogu.org/problemnew/solution/P1020
基本思路:
首先第一问是一个求最长下降子序列的问题,但是不能用传统的方法,因为会超时。还有个比较蛋疼的地方就是输入的时候,没有指定输入数据的个数,这个我也不会 ,看了题解才知道那么输入的。首先,基本的思路还是和传统的求最长上升(下降)子序列一样的,都是求以i为结尾的最长上升(下降)子序列,但是第2重循环可就大大不一样的,传统的是依次枚举以(1~~i-1)上的数为结尾的最长上升(下降)子序列,如果满足a[i]<a[j]或者a[i]>a[j],就执行dp[i]=max(dp[i],dp[j]+1);最终找出dp数组中最大的一个,就是结果。这是传统的解法。但是此题的第二重循环是依次枚举前i-1个数中所求得的递增(递减)子序列的长度(注意:是从最长的到最短的这个顺序开始枚举的 这很关键)
最终找到dp数组中的最大值,输出即可
代码如下:
#include<bits/stdc++.h>
using namespace std;
int visited[150000];//动归用的数组
int a[150000];
int t=0;//t表示当前所得到的最长上升子序列或最长下降子序列的长度
int z=0;//数据大小
int d1[150000],d2[150000];//d1[i],d2[i]表示子序列长度为i时上升(下降)子序列的最后一个元素在数组中的下标
int main()
{
while(~scanf("%d",&a[++z]));//学到的新知识,对于不给定输入个数的数据的输入可以这样输入,也可以不等于EOF的那样输入
z--;
for(int i=1;i<=z;i++)//从这一行到25行是求的最长递减子序列(全新的方法,以前根本没用过,涨姿势了)
{
visited[i]=1;//因为此题对于时间复杂度的要求极高,所以把visited数组的初始化加入到dp过程中
for(int j=t;j>=1;j--)//这个for循环的意思是从当前找到的最长的递减子序列开始枚举,如果一旦遇到满足下面if条件的,直接跳出这个for循环,更新t和d1[]数组的值
//因为这是从最长到最短枚举的,如果一旦遇到满足的,就不用再往下枚举了,因为即使下面的点也有满足条件的,+1之后也不可能比第一次遇到的满足条件的那个所算出来的数大
{
if(a[i]<=a[d1[j]])
{
visited[i]=visited[d1[j]]+1;//其实visited[d1[j]]就相当于j,之所以写成这个,是为了看起来更像动归
break ;
}
}
t=max(t,visited[i]);//这一步除了更新t之外,还可以寻找最后计算完成后visited数组中的最大值
d1[visited[i]]=i;
}
cout<<endl;
cout<<t<<endl;
t=0;//下面的代码和上面的差不多,只不过这是求最长上升子序列
for(int i=1;i<=z;i++)
{
visited[i]=1;
for(int j=t;j>=1;j--)
{
if(a[i]>a[d2[j]])
{
visited[i]=visited[d2[j]]+1;
break ;
}
}
t=max(t,visited[i]);
d2[visited[i]]=i;
}
cout<<endl;
cout<<t<<endl;
}
至于第二问为是求最长递增子序列 原因如下:
(1)假设打导弹的方法是这样的:取任意一个导弹,从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组,再在没打下来的导弹中任选一个重复上述步骤,直到打完所有导弹。
(2)假设我们得到了最小划分的K组导弹,从第a(1<=a<=K)组导弹中任取一个导弹,必定可以从a+1组中找到一个导弹的高度比这个导弹高(因为假如找不到,那么它就是比a+1组中任意一个导更高,在打第a组时应该会把a+1组所有导弹一起打下而不是另归为第a+1组),同样从a+1组到a+2组也是如此。那么就可以从前往后在每一组导弹中找一个更高的连起来,连成一条上升子序列,其长度即为K;
(3)设最长上升子序列长度为P,则有K<=P;又因为最长上升子序列中任意两个不在同一组内(否则不满足单调不升),则有
P>=K,所以K=P。
这是一种新的求最长子序列的方法 此萌新第一次见到,涨姿势了 O(∩_∩)O哈哈哈~