BZOJ 1264 AHOI2006 基因匹配Match 动态规划+树状数组
2023-09-11 14:14:09 时间
题目大意:给定n个数和两个长度为n*5的序列,每一个数恰好出现5次,求两个序列的LCS
n<=20000。序列长度就是10W。朴素的O(n^2)一定会超时
所以我们考虑LCS的一些性质
LCS的决策+1的条件是a[i]==b[j] 于是我们记录a序列中每一个数的5个位置
扫一下b[i] 对于每一个b[i]找到b[i]在a中的5个位置 这5个位置的每一个f[pos]值都能够被b[i]更新 于是找到f[1]到f[pos-1]的最大值+1 更新f[pos]就可以
这个用树状数组维护 时间复杂度O(nlogn)
非常难想的一道题 只是不难写
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 200200 using namespace std; int n,ans,a[M*5],b[M*5],c[M*5],f[M*5],pos[M][6]; void Update(int x,int y) { for(;x<=n*5;x+=x&-x) c[x]=max(c[x],y); } int Get_Ans(int x) { int re=0; for(;x;x-=x&-x) re=max(re,c[x]); return re; } int main() { int i,j; cin>>n; for(i=1;i<=n*5;i++) { scanf("%d",&a[i]); pos[ a[i] ][ ++pos[a[i]][0] ]=i; } for(i=1;i<=n*5;i++) scanf("%d",&b[i]); for(i=1;i<=n*5;i++) { for(j=5;j;j--) { int k=pos[b[i]][j]; f[k]=max( f[k] , Get_Ans(k-1)+1 ); Update(k,f[k]); ans=max(ans,f[k]); } } cout<<ans<<endl; }
相关文章
- 机器人中的轨迹规划(Trajectory Planning )
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 629 K个逆序对数组(动态规划+数学)
- LeetCode-801. 使序列递增的最小交换次数【动态规划,滚动数组】
- 基于改进粒子群优化算法的UAV三维路径规划研究(Matlab代码实现)
- m基于GA遗传优化的AGV栅格地图路径规划和避障matlab仿真
- m基于自适应遗传优化的IEEE-6建设费用和网络损耗费用最小化电网规划算法matlab仿真
- 714. 买卖股票的最佳时机含手续费-动态规划算法
- 1191. K 次串联后最大子数组之和-暴力动态规划,和优化算法
- 915. 分割数组-动态规划算法
- 152. 乘积最大子数组-动态规划
- [LeetCode] 63. 不同路径 II ☆☆☆(动态规划)
- poj2728 Desert King --- 01分数规划 二分水果。。
- POJ 1160 Post Office (动态规划)
- 【BZOJ3627】【JLOI2014】路径规划 分层图
- HDU4689Derangement (动态规划)
- 读书笔记:《敏捷估计与规划》
- 软件测试基础(一)——对软件测试了解发展规划和什么是软件和软件的特性
- DFS和动态规划——字符串匹配 真蛋疼 为*的情况需考虑匹配0个、1个、2个情况 DFS会超时 正则匹配的话 需要向前看x*的情况 打包处理
- 云计算|OpenStack|社区版OpenStack安装部署文档(一 --- 前期硬件准备和部署规划)
- kingbase之集群部署之集群规划和安装
- Kubernetes 企业集群建设规划