【CSP模拟赛】凤凰院凶真(最长公共上升子序列)
题目描述
α世界线.凤凰院凶真创立了反抗SERN统治的组织“瓦尔基里”.为了脱离α线,他需要制作一个世界线变动率测量仪.
测量一个世界线相对于另一个世界线的变动率,实质上就是要求出这两个世界线的最长公共合法事件序列.
一个世界线的事件逻辑序列是一个正整数序列,第k个数表示第k个事件发生的时间.对于一个世界线,一个合法的事件序列是事件逻辑序列的一个子序列,满足时间严格递增.
现在,对于两个不同的世间线α,β求出最长的一个事件序列,满足这个序列在α,β世界线中均是合法的.这个序列也就是之前提到过的最长公共合法事件序列.
输入描述
第一行一个整数n,表示世界线α的事件个数.
第二行n个整数a1;a2......an,表示世界线的事件逻辑序列.
第三行一个整数m,表示世界线β的事件个数.
第四行m个整数b1;b2......bm,表示世界线的事件逻辑序列.
输出描述
第一行一个整数k,表示最长公共合法事件序列的长度.
第二行k个整数,表示最长公共合法事件序列.如果有多解,输出任意一个.
样例输入
5
1 4 2 5 1
4
1 1 2 4
样例输出
2
1 4
分析
虽然听机房的大佬们说这是一道最长公共上升子序列的板子题,然而我不会。。。。。。
根据最长公共序列的求法,可以考虑二维状态dp[i][j]
如果dp[i][j]表示a序列前i个事件,b序列前j个事件构成的最长公共上升子序列的长度,转移时因为不知道最后一项的大小所以无法转移
如果dp[i][j]表示a序列第i个事件,b序列第j个事件作为结尾的最长公共上升子序列的长度,转移时因为不知道前一项在哪里所以要疯狂枚举状态从而达到O(n^4)的优秀复杂度
可以试着折中一下,
用dp[i][j]表示a序列前i个事件,b序列前j个事件构成且以b序列的第j个事件为结尾的最长公共上升子序列的长度。
所以dp[i][j]就可以由dp[i-1][1~j-1]转移过来,而且这个东西还可以利用单调性优化
因为更新dp[i]这一维的时候,i是不变的,所以可以一遍dp一遍存下并维护dp[i-1][1~j](a[i]>b[j])的最大值
这样就可以从O(n^3)优化到O(n^2)了 只有我这样的菜文鸡一个板题才写这么多东西
Code
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,x,y,en,ans,a[maxn],b[maxn],sta[maxn],dp[maxn][maxn],pre[maxn][maxn];
int main()
{
scanf("%d",&n);for(int i=;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);for(int i=;i<=m;i++)scanf("%d",&b[i]);
for(int i=;i<=n;i++)for(int j=;j<=m;j++)
{
dp[i][j]=dp[i-][j];
if(b[j]==a[i])dp[i][j]=dp[i-][pre[i][]]+,pre[i][j]=pre[i][];
if(b[j]<a[i]&&dp[i-][pre[i][]]<dp[i-][j])pre[i][]=j;
if(ans<dp[i][j]&&a[i]==b[j])ans=dp[x=i][y=j];
}
printf("%d\n",ans);
do
{
sta[++en]=b[y];y=pre[x][y];
while(a[x]!=b[y])x--;
}while(y);
while(en)printf("%d%c",sta[en],en==?'\n':' '),en--;
}
最新文章
- linux c++循环缓冲区模板类
- atitit.文件上传带进度条的实现原理and组件选型and最佳实践总结O7
- MAPR 开发环境搭建过程记录
- zw版【转发&#183;台湾nvp系列例程】HALCON ShapeTrans(Delphi)
- .net remoting 客户端与服务端绑定事件,一部电脑当服务器,另一部当客户端,发布后没法接收远程错误信息。
- 如何在KVM中管理存储池
- Python金融应用编程(数据分析、定价与量化投资)
- how to increase an regular array length in java?
- Prism for WPF再探(基于Prism事件的模块间通信)
- 全网最详细的Windows里Anaconda-Navigator启动后闪退的解决方案(图文详解)
- UltraEdit使用(工具类似于notepad++)
- EF code first 迁移问题
- Centos7.5 防火墙设置
- POJ 3259 Wormholes(bellman_ford,判断有没有负环回路)
- POJ 1451 T9 (字典树好题)
- [na]交换机原理/macof
- 洛谷P1083 借教室 NOIP2012D2T2 线段树
- POJ1410_还是没考虑全面——线段是否与矩形有共同的垂直投影
- 变不可能为可能 - .NET Windows Form 改变窗体类名(Class Name)有多难?续篇
- 常用的Jquery工具方法