bzoj 5454: Subsequence

题意

给出两个由小于等于k的正整数构成的数列A与B，长度为n与m
现在需要一个由小于等于k的正整数构成的数列C，使得C既不是A的子序列，也不是B
的子序列，请求出C的最小长度

题解

继续开发第45版。。

有两个做法，都说一说把

看到序列自然想到序列自动机
建立自动机
然后bfs一下
$f[x][y]$表示第一个串到$x$，第二个串到$y$的最短步数
然后$O(k)$转移？
最后$f[0][0]$就是答案
看起来复杂度是$O(n{k}^2)$的
但是实际上，$f$有值的不多，所以跑得飞快

PP说序列自动机的题都可以用DP来解决
那么我们就来考虑DP
考虑我给你一个串
我们怎么判断答案
自然是DP
一位一位插入
$f_{i,j}$表示第一个串匹配到$i$，第二个匹配到$j$是否可能
然后如果最后有任何一个位置OK就是存在了
考虑用DP模拟这个过程
$f_{i,j}$表示第一个串匹配到$i$，第二个匹配到$j$的最小步数是什么
然后每一次也是$O(k)$转移
转移到什么呢？
当然是转移到$i$后面的第一个$k$，$j$后面的第一个$k$啊
如果不存在这个k，就可以输出答案了
看起来也是$O(nmk)$
但是实际上跑得飞快

或许可以证明是更优的复杂度？
但是我不会证
当然我也没想证
我认为是没有办法卡掉的
欢迎hack（大雾

CODE（序列自动机）:

 
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=4005;
int n,m,k,ans;
struct qq
{
    short int son[N][N];short int par[N];short int last[N];short int tot;void Ins (int x){
    int np=++tot;for (int i=1;i<=k;i++)for (int j=last[i];j!=0&&son[j][x]==0;j=par[j])son[j][x]=np;par[np]=last[x];    last[x]=np;}
}a,b;
struct qt
{
    short int rt1,rt2,dep;qt () {
    };qt (short int _rt1,short int _rt2,short int _dep)   {
    rt1=_rt1;rt2=_rt2;dep=_dep;}
};
bool vis[N][N];
void bfs ()
{
    queue<qt> q;q.push(qt(1,1,0));while (!q.empty()){
    qt x=q.front();q.pop();for (int u=1;u<=k;u++){
    int y=a.son[x.rt1][u],z=b.son[x.rt2][u];if (vis[y][z]) continue;vis[y][z]=true;if (y==0&&z==0){
    printf("%d\n",x.dep+1);return ;}q.push(qt(y,z,x.dep+1));}}
}
int main()
{
    memset(vis,false,sizeof(vis));scanf("%d%d%d",&n,&m,&k);ans=n+m+1;for (int u=1;u<=k;u++)   b.last[u]=a.last[u]=1;for (int u=1;u<=n;u++){
    int x;scanf("%d",&x);a.Ins(x);}for (int u=1;u<=m;u++){
    int x;scanf("%d",&x);b.Ins(x);}bfs();return 0;
}
?