???求助求助告急告急!!!

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

BeingErnest @ 2018-11-09 10:20:14

这个代码在友好城市是过的了的,按理说跟本题差不多,可就是莫名WA,求解求改求.....

struct dp
{
int a,b;
}p[5000000];
int top=0,s[5000000];
bool cmp(dp a,dp b)
{
        return a.a<b.a;
}
int main()
{
int n;
memset(s,0,sizeof(s));
scanf("%d",&n);
for(int i=1;i<=n;i++)
    scanf("%d",&p[i].a);
for(int i=1;i<=n;i++)
    scanf("%d",&p[i].b);
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
    if(p[i].b>=s[top]) s[++top]=p[i].b;
        else s[lower_bound(s,s+top,p[i].b)-s]=p[i].b;
}
printf("%d",top);
return 0;
}

by StudyingFather @ 2018-11-09 10:24:42

@铭玘 这题是LCS啊,不是LIS...


by BeingErnest @ 2018-11-09 10:27:57

题解里说可以通过映射来转换成LIS


by BeingErnest @ 2018-11-09 10:29:00

@StudyingFather 友好城市本身看起来像LCS,但大佬转换成来LIS


|