首页 > 其他分享 >51nod-基因匹配+luogu-【模板】最长公共子序列

51nod-基因匹配+luogu-【模板】最长公共子序列

时间:2024-07-27 09:39:20浏览次数:14  
标签:51nod luogu s1 int https s2 com 模板

https://www.luogu.com.cn/problem/P1439

https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338

以上两个都是特例,一个是每个元素不重复,一个是每个元素均有5个。

image-20240727093531395

正确性说明参考:https://www.luogu.com.cn/article/1bcs9052

由于一般情况可能出现多个,就需要类似于上面的处理,倒序是防止一组内选取多个,多个编号是因为只要满足下标中任意一个均可。

优化可以考虑二分或者树状数组(因为离散化过,比较方便了)。

复杂度 \(O(25n\log25n)\)。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[5*N],n5,s1[N],s2[N],n,t[N][6],f[5*N],c[5*N];
void add(int x,int v){
	for(;x<=n5;x+=x&-x)c[x]=max(c[x],v);
}
int sum(int x){
	int res=0;
	for(;x;x-=x&-x)res=max(res,c[x]);
	return res;
}
int main(){
	#ifdef LOCAL
	freopen("1.txt","r",stdin);
	#endif
	#ifndef LOCAL
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	#endif
	cin>>n;
	n*=5;
	for(int i=1;i<=n;++i)cin>>s1[i],t[s1[i]][++t[s1[i]][0]]=i;
	for(int i=1;i<=n;++i){
		cin>>s2[i];
		for(int j=5;j;--j)
			a[++n5]=t[s2[i]][j];
	}
	int ans;
	for(int i=1;i<=n5;++i){
		f[i]=sum(a[i]-1)+1;
		add(a[i],f[i]);
		ans=max(ans,f[i]);
	}
	cout<<ans;
	return 0;
}

标签:51nod,luogu,s1,int,https,s2,com,模板
From: https://www.cnblogs.com/wscqwq/p/18326647

相关文章

  • Luogu P3177 树上染色 [ 蓝 ] [ 树形 dp ] [ 贡献思维 ]
    一道很好的树形dp!!!!!树上染色。错误思路定义\(dp[u][i]\)表示以\(u\)为根的子树中,把\(i\)个点染成黑色的最大收益。但这样写,就在转移的时候必须枚举每一个点,复杂度过大,而且还不好写,是十分错误的写法。正确思路一般看到有关树上“路径”的题,就要把路径拆成一个个独立的......
  • SpringBoot Thymeleaf 模板标签
    扩展Thymeleaf模板标签上一篇我们写到SpringBoot依赖之Thymeleaf模版引擎的使用,当时只列举了简单文本标签,下面针对多标签进行分析和分享。Thymeleaf的模板标签,包括文本显示、属性设置、条件判断、循环迭代、表单处理、片段引用、国际化支持等常用功能。我们尽可能......
  • 易优CMS模板标签ui开关标签
    【基础用法】标签:ui描述:可视化类型的模板必须引入的主标签,建议在html代码的body底部引入,该标签包含外观调试通用的css、js。用法:{eyou:uiopen='off'/}属性:open=''是否开启,on为开启,off为关闭涉及表字段:无  【更多示例】-------------------------------示例1----------......
  • 易优CMS模板标签SQL数据查询查询数据表ey_arctype,指定栏目ID的基本信息,不使用数据缓存
    【基础用法】标签:sql描述:用于获取MySQL数据库内容的标签。用法:{eyou:sqlsql=''cachetime='3600'empty='没有数据'}{$field.数据表相应的字段名称}{/eyou:sql}属性:sql=''需要查询的SQL语句cachetime='3600'数据缓存时间,默认缓存25小时,即86400秒empty=''没有数据时显示......
  • 函数模板重载和实例化例题
    //CPPTest.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。//#include<fstream>#include<iostream>#include<string>#include<cstring>#include<cmath>usingnamespacestd;template<classT>Tmaxn(T*arr,intn){ Tmax......
  • 手写模板的设计
    手写模板的设计本教程由做字体网(www.zuoziti.com)友情提供!本教程是制作手写字体系列教程,建议从序言部分开始阅读学习!如需交流,请加QQ924268440本节视频教程先看一下模板样子从这一节我们正式开始制作手写字体,制作手写字体的第一步就是制作手写字体模板,先看一下我的模......
  • C++ primer plus 第16章string 类和标准模板库, 函数符概念
    C++primerplus第16章string类和标准模板库,函数符概念C++primerplus第16章string类和标准模板库,函数符概念文章目录C++primerplus第16章string类和标准模板库,函数符概念16.5.1函数符概念程序清单16.15functor.cpp16.5.1函数符概念正如STL定......
  • C++ primer plus 第16章string 类和标准模板库, 函数对象
    C++primerplus第16章string类和标准模板库,函数对象C++primerplus第16章string类和标准模板库,函数对象文章目录C++primerplus第16章string类和标准模板库,函数对象16.5函数对象16.5函数对象很多STL算法都使用函数对象–也叫函数符(fiunctor)。......
  • 网站源码装饰公司pbootcms模板网页设计主题
    装饰公司的网站设计分享我很高兴向大家介绍我刚刚制作的装饰公司的网站设计。友好的站点界面,是打动访客的第一步。装饰公司网站的主题网站设计通常需要考虑多个方面,以确保网站能够有效地展示公司形象、吸引潜在客户并提升业务。以下是对装饰公司网站主题设计的详细介绍:一、......
  • t4模板无法加载文件或程序集system.runtime
        在.net6.0环境下使用T4模板生成代码报错错误正在运行转换:System.IO.FileNotFoundException:未能加载文件或程序集“System.Runtime,Version=6.0.0.0,Culture=neutral,PublicKeyToken=b03f5f7f11d50a3a”或它的某一个依赖项。系统找不到指定的文件。......