[关闭]
@zzzc18 2017-11-09T11:47:26.000000Z 字数 462 阅读 1087

最长公共子序列

模板库


地址

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 100000+9;
  6. int n;
  7. int b[MAXN];
  8. int num[MAXN];
  9. int dp[MAXN];
  10. void solve(){
  11. memset(dp,0x7f,sizeof(dp));
  12. for(int i=1;i<=n;i++){
  13. int loc=upper_bound(dp+1,dp+n+1,num[i])-dp;
  14. dp[loc]=num[i];
  15. }
  16. printf("%d\n",lower_bound(dp+1,dp+n+1,dp[0])-(dp+1));
  17. }
  18. int main(){
  19. scanf("%d",&n);
  20. for(int i=1;i<=n;i++){
  21. int x;scanf("%d",&x);
  22. b[x]=i;
  23. }
  24. for(int i=1;i<=n;i++){
  25. int x;
  26. scanf("%d",&x);
  27. num[i]=b[x];
  28. }
  29. solve();
  30. return 0;
  31. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注