Cydiater

「雅礼集训 2017 Day4」猜数列

有一个长度为 $m$ 的,由 $1$ 到 $9$ 之间的数构成的未知数列 $a_m$。

你现在有 $n$个线索,每个线索都是用如下方式生成的:

  • 选择序列 $a_m$ 的某一个位置 $p$ 作为开始;
  • 选择某个方向(向左或向右);
  • 从 $p$ 出发往你选择的方向走,每遇到一个之前未出现的数就将它加到线索中。

现在你需要求出满足所有线索的长度最小的序列的长度。

这道题搞了好几天,网上没题解我就做一点微小的贡献吧~

看到这道题的数据范围,很明显是要状压了。我们发现数据范围里有所有方向都一致的部分分,所以可以先考虑当所有方向都一样时怎么处理。很容易设计出来一个状态 $f(S)$为当前已经匹配完的状态为$S$时的最短长度,考虑如何转移,我们预处理,得到序列$k$是否可以从序列$i$的第$j$个数开始匹配。然后就可以很方便的转移了。

接着考虑如何处理不同方向的,容易发现,当我们从右向左 DP 时,对于方向向右的,已经匹配好的是一个后缀,而对于方向向左的,已经匹配好的是一个前缀。所以我们设计状态$f(x, cx, y, cy, S)$来表示对于方向向右的序列$x$,从第$cx$开始,没有匹配上,对于方向向左的序列$y$,从$cy$开始没有匹配上。

然后考虑怎么处理转移,对于方向向右的,当其$cx$移动到终点时即$x$的匹配完成,枚举所有没有处于匹配状态的序列,看看是否能在某个位置和$x$衔接上。对于方向向左的,同样枚举所有序列,看看能否用新的序列的状态来替代当前的匹配。然后当我们向左边扩展时,分三种情况讨论即可,不再详细说明。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 11;
const int oo = 0x3f3f3f3f;

int N, a[MAXN][MAXN], n[MAXN], s[MAXN][MAXN];
bool vaild[MAXN][MAXN][MAXN];

int f[MAXN][MAXN][MAXN][MAXN][bin(MAXN)];

inline bool chk(int x, int m, int y){
    if ((~s[x][n[x]]) & s[y][n[y]]) return 0;
    up (i, 1, n[y]) m += a[y][i] == a[x][m];
    return m == n[x] + 1;
}

int DP(int x, int cx, int y, int cy, int ss){
    if (f[x][cx][y][cy][ss] != -1) return f[x][cx][y][cy][ss];
    if (cx == 0 && cy == n[y] + 1 && ss == bin(N) - 1) 
        return f[x][cx][y][cy][ss] = 0;
    int res = oo;
    if (cx == 0) {
        up (i, 0, N - 1) if (!(bin(i) & ss)) 
            up (j, 1, n[i] + 1) if (vaild[i][j][x])
                cmin(res, DP(i, j - 1, y, cy, ss | bin(i)));
    }else {
        up (i, 0, N - 1) if (!(bin(i) & ss) && vaild[y][cy][i]) 
            cmin(res, DP(x, cx, i, 1, ss | bin(i)));
        up (i, 1, 9) {
            int p = a[x][cx] == i;
            int q = a[y][cy] == i;
            if (p && q) cmin(res, DP(x, cx - 1, y, cy + 1, ss) + 1);
            if (p && (bin(i) & s[y][cy - 1])) cmin(res, DP(x, cx - 1, y, cy, ss) + 1);
            if (q && (bin(i) & s[x][cx])) cmin(res, DP(x, cx, y, cy + 1, ss) + 1);
        }
    }
    return f[x][cx][y][cy][ss] = res;
}

int main(){
    scanf("%d", &N);
    up (i, 0, N - 1) {
        while (scanf("%d", &a[i][++n[i]]) != EOF && a[i][n[i]] != 0);
        n[i]--;
        up (j, 1, n[i]) s[i][j] = s[i][j - 1] | bin(a[i][j]);
    }
    s[N][0] = -1;
    up (i, 0, N) up (j, 1, n[i] + 1) up (k, 0, N - 1) 
        vaild[i][j][k] = chk(i, j, k);
    int ans = oo;
    memset(f, -1, sizeof(f));
    up (i, 0, N - 1) cmin(ans, DP(i, n[i], N, 1, bin(i)));
    printf("%d\n", ans == oo ? -1 : ans);
    return 0;
}