CF750E New Year and Old Subsequence solution

· · 题解

CF750E New Year and Old Subsequence

solution

我们用 f_{i,k} 表示考虑到第 i 位，要有 2017 的前 k 位的子序列并且不包含 2016 最少要用几个数。

然后就可以把 \text{dp} 方程写出来

f_{i,0}=f_{i-1,0} + [s_i=2] f_{i,1}=\min\{f_{i-1,1} + [s_i=0],\text{if}[s_i = 2]f_{i-1,0}\} f_{i,2}=\min\{f_{i-1,2} + [s_i=1],\text{if}[s_i = 0]f_{i-1,1}\} f_{i,3}=\min\{f_{i-1,3} + ([s_i=7] \text{or} [s_i=6]),\text{if}[s_i = 1]f_{i-1,2}\} f_{i,4}=\min\{f_{i-1,4} + [s_i=6],\text{if}[s_i = 7]f_{i-1,3}\}

注意到后面的转移中条件如果不成立则不能转移。

接着我们发现题目把这个东西转换成了区间问题，于是乎我们就采用动态 \text{dp} 的套路去写这个 \text{dp} 式。

\begin{bmatrix} f_{i - 1,0} & f_{i - 1,1} & f_{i - 1,2} & f_{i - 1,3} & f_{i - 1,4} \end{bmatrix} * \begin{bmatrix} a & b & c & d & e \\ f & g & h & i & j \\ k & l & m & n & o \\ p & q & r & s & t \\ u & v & w & x & y\end{bmatrix} = \begin{bmatrix} f_{i,0} & f_{i,1} & f_{i,2} & f_{i,3} & f_{i,4} \end{bmatrix}

为了方便写，我用 x\to0 表示如果 x=1，则值为 0，否则为无穷大。

接着就硬解这个矩阵，解出来会长这个样子。

\begin{bmatrix} [s_i=2] & s_i=2\to 0 & inf & inf & inf \\ inf & [s_i=0] & s_i=0\to 0 & inf & inf \\ inf & inf & [s_i = 1] & s_1 = 1\to 0 & inf \\ inf & inf & inf & [s_i=7] \text{or} [s_i=6] & s_i=7\to 0 \\ inf & inf & inf & inf & [s_i=6]\end{bmatrix}

然后就把这个东西扔到线段树里就 \text{OK} 了。

code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
constexpr int inf = 0x3f3f3f3f;
struct Matrix {
    int mat[5][5];
    inline Matrix operator*(const Matrix &b) const {
        Matrix c;
        memset(c.mat, 0x3f, sizeof(c.mat));
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                for (int k = 0; k < 5; k++) c.mat[i][j] = min(mat[i][k] + b.mat[k][j], c.mat[i][j]);
        return c;
    }
} w[N << 2];
int n, q;
char s[N];
inline void pushup(int u) { w[u] = w[u << 1] * w[u << 1 | 1]; }
void build(int u, int L, int R) {
    if (L == R) {
        char c = s[L];
        w[u] = (Matrix){{{c == '2', c == '2' ? 0 : inf, inf, inf, inf},
                         {inf, c == '0', c == '0' ? 0 : inf, inf, inf},
                         {inf, inf, c == '1', c == '1' ? 0 : inf, inf},
                         {inf, inf, inf, c == '7' || c == '6', c == '7' ? 0 : inf},
                         {inf, inf, inf, inf, c == '6'}}};
        return;
    }
    int M = L + R >> 1;
    build(u << 1, L, M), build(u << 1 | 1, M + 1, R);
    pushup(u);
}
Matrix query(int u, int L, int R, int l, int r) {
    if (L >= l && R <= r) return w[u];
    int M = L + R >> 1;
    if (M >= r) return query(u << 1, L, M, l, r);
    if (M < l) return query(u << 1 | 1, M + 1, R, l, r);
    return query(u << 1, L, M, l, r) * query(u << 1 | 1, M + 1, R, l, r);
}
int main() {
    cin >> n >> q;
    scanf("%s", s + 1), build(1, 1, n);
    int l, r;
    while (q--) {
        scanf("%d %d", &l, &r);
        Matrix ans = query(1, 1, n, l, r);
        printf("%d\n", ans.mat[0][4] <= n ? ans.mat[0][4] : -1);
    }
    return 0;
}