30分,萌新刚学LIS,求dalao帮忙一下

P1439 【模板】最长公共子序列

OvCherryBlossomRain @ 2021-03-19 16:56:33

请求dalao帮忙,评测过的#1,#2,#3。

4数据我调试过,发现是比答案少了1。但是我自己调试了一下代码,觉得没问题.....不知道错哪了。(个人感觉应该是height数组可能有问题,但是自己试过一些数据,发现都没问题。)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int a[maxn],d[maxn],height[maxn],n;
int LIS(){
    int len = 1;
    d[1] = height[1];
    for(int i=2;i<=n;i++){
        if(height[i]>d[len]){
            d[++len] = height[i];
        }else{
            int j = lower_bound(d+1,d+len+1,height[i])-d;
            d[j] = height[i];
        }
    }
    return len;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&height[a[i]]);
    //for(int i=1;i<=n;i++) cout<<height[i]<<' ';cout<<endl;
    printf("%d",LIS());
    return 0;
}

by Lucifero @ 2021-03-19 17:08:58

LIS = 最长上升子序列

LCS = 最长公共子序列


by _jimmywang_ @ 2021-03-19 17:26:06

望丰展?使MD


by OvCherryBlossomRain @ 2021-03-19 22:17:45

@Gray_White 但是LCS的dp求法在这道题不行吧。。。因为它是10000的数据量.....平方会被卡掉。


by OvCherryBlossomRain @ 2021-03-19 22:21:32

@the_tool_er dalao说的是排版问题吗。。。我这边看代码的排版是正常的。。。就是正常显示。。我也是用洛谷帖子的“插入代码”再发上去的。。。。


by 老牧童与戈戈 @ 2021-05-29 07:27:47

@OvCherryBlossomRain 要用 O(nlogn) 的做法


by OvCherryBlossomRain @ 2021-05-29 16:47:26

@老牧童与戈戈 嗯,好,感谢,我已经找到方法转换成nlogn的做法了。


|