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