「FZOJ3827」题解

题意

给定一个长度为$n$和一个长度为$m$的序列$A$和$B$

求$A$和$B$有多少个非空公共子序列满足$\forall a,b$在子序列中相邻,有向边$<a,b>\in 边集E$

答案对$10^9+7取模$

分析

显然是DP,设$f_{i,j}$为以$A$序列第$i$个元素$B$序列第$j$个元素结尾的方案数($a_i\neq b_j$时$f_{i,j}=0$)
令$g_{i,j}=\sum^i_{k=1}f_{k,j}$
如图(上方为$B$下方为$A$)
很明显$g$可以用前缀和维护
现在开始考虑相邻元素的限制,对于$b_j$考虑其到$a_i$是否有边,如果有,其对$f_{i,k}(k>j,a_i=b_k)$有$g_{i-1,j}$的贡献($\forall l\in[1,i-1]:a_l=b_j很明显f_{l,j}$可以转移到$f_{i,k}(k>j,a_i=b_k$)
$h_{i,j}=\sum_{k\in[1,j-1],<b_k,a_i>\in E}g_{i,k}$
如图(上方为$A$下方为$B$)
由于枚举$j$时$i$是固定的,所以我们可以用前缀和统计
$h_{i,j}=
\begin{cases}
h_{i,j-1}+g_{i,j} & <b_j,a_i>\in E \\
h_{i,j-1} & <b_j,a_i>\notin E \\
\end{cases}$
$f_{i,j}=h_{i,j-1}+1$(还有不用前面的,从$a_i,b_j$开始的情况,贡献为1)

$f$不参加转移,只计入答案
$g$可以用滚动数组
$h_{i-1}$与$h_{i}$无关,用临时变量记录即可
维护时,先用$h$算得$f$,再用$g$更新$h$,最后用$f$更新$g$

原数组要离散化一下

时间复杂度$O(n\cdot m)$
空间复杂度$O(n\cdot m)$

代码

const int N = 3005;
const int Mod = 1000000007;

void add(int &, int);

int a[N], b[N];
bool ok[N][N];
std::map<int, int> mp;
int g[2][N];

int main () {
  int n, m, k;
  read(n), read(m), read(k);
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    if (!mp[a[i]]) {
      mp[a[i]] = ++cnt;
    }
    a[i] = mp[a[i]];
  }
  for (int i = 1; i <= m; ++i) {
    read(b[i]);
    if (!mp[b[i]]) {
      mp[b[i]] = ++cnt;
    }
    b[i] = mp[b[i]];
  }
  for (int i = 1; i <= k; ++i) {
    int u, v;
    read(u), read(v);
    u = mp[u], v = mp[v];
    if (!u || !v) {
      continue;
    }
    ok[u][v] = true;
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int h = 0;
    for (int j = 1; j <= m; ++j) {
      g[i & 1][j] = g[(i & 1) ^ 1][j];
      int f = 0;
      if (a[i] == b[j]) {
        f = h + 1;
        add(ans, f);
      }
      if (ok[b[j]][a[i]]) {
        add(h, g[i & 1][j]);
      }
      add(g[i & 1][j], f);
    }
  }
  write(ans), EL;
  return 0;
}

inline void add(int &i, int j) {
  i = (i + j) % Mod;
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2019/fzoj-3827/