Ad-hoc 题
这里仅考虑 \(f>g\)
考虑暴力 dp
\(dp_{i,j}\) 表示第一个序列遍历到 \(i\) 项，第二个序列遍历到 \(j\) 项。
容易得到转移式子 \(dp_{i,j} = [a_i>b_j]\times [dp_{i-1,j}|dp_{i-1,j-1}|dp_{i,j-1}]\)
类似一个二维平面游走问题？
考虑抽象问题：对于一个 \(n\times m\) 的二维平面，\((i,j)\) 只有在 \(a_i>b_j\) 的时候才是有效点，求从 \((1,1)\) 通过往右往下或往右下的操作是否可以到 \((n,n)\)。默认 \((1,1)\) 和 \((n,n)\) 都是有效点。
发现不合法情况较少，有且仅有以下情况：
- 一整行都是非有效点。
- 一整列都是非有效点。
- 起点被横竖 L 型非有效点包围。
- 重点被横竖 L 型非有效点包围。
带入式子分析可以得到四条可行的式子
-
\(\max x \ge \max y\)
-
\(\min x\ge\min y\)
-
\(\exists (i,j), x_i\ge \max_{k=1}^j(y_k)， y_j \le \min_{k=1}^i x_k\)
-
\(\exists (i,j),x_i\ge \max_{k=j}^{m} (y_k），y_j\le \min_{k=i}^n x_k\)
后两个双指针即可。