P3685 [CERC2016] Invisible Integers 题解

· · 题解

对于方向相同的两个提示 x,y，我们考虑如果 y 能接在 x 的第 i 位之后，应当满足什么条件：

如果我们按这个方向依次填数，若已经填到了 x 的第 i 位，那么我们可以选择停止考虑 x，转而考虑 y。

若 i 满足条件，则 i+1 也满足条件。我们可以对于每对 (x,y) 预处理出这个最小的 i，或者发现不存在这样的 i。

（以下所有下标均从 0 开始。记 a_{i,l} 表示提示 i 的第 l 位；p_{i,l} 表示数字 l 在提示 i 中的出现位置，若没有出现则为 +\infty；L_i 表示提示 i 的长度）

考虑如果只能往右走怎么做。我们从左到右依次填数。考虑 DP，设 f(S,i,l) 表示已经考虑了集合 S 中的提示，当前正在考虑提示 i，已经填了 i 的第 0\sim l-1 位（正在等待第 l 位）时的最短长度。有两种转移：

考虑扩展到一般情况。设 f(S,i,l,j,r) 表示已经考虑了集合 S 中的提示，当前正在考虑的向左走的提示为 i，已经填了 i 的第 l\sim L_i-1 位（正在等待第 l-1 位），当前正在考虑的向右走的提示为 j，已经填了 j 的第 0\sim r-1 位（正在等待第 r 位）时的最短长度。

注意：我们仍然是从左到右依次填数，所以向左走的提示要从后往前匹配，向右走的提示要从前往后匹配，这导致了两个方向的提示转移方式的不同。

有三种转移：

有亿点细节：

我们需要想办法记录当前考虑的提示是否为对应方向的第一个提示。具体地，我们可以新增一个编号为 n 的提示作为占位符（可以认为它的长度为 0）。在 f(S,i,l,j,r) 中，若 i=n，则表示不再新增向左的提示；若 j=n，则表示还没有考虑过向右的提示。

DP 初值为 f(\varnothing,n,0,n,0)=f(\{i\},i,L_i,n,0)=0。需要新增一种转移：

注意转移顺序。时间复杂度 \mathcal{O}(2^n (10n)^2\cdot n)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,ht[15][15],pos[15][15],st[15],len[15],tr[15][15];
int f[1029][11][11][11][11],cur,ans;
inline int get_tr(int x,int y){
    if((st[x]&st[y])^st[y])return inf;
    int a=pos[y][ht[x][len[x]-1]],b,i;
    if(a==inf)return len[x];
    for(i=len[x]-1;i;--i){
        b=a,a=pos[y][ht[x][i-1]];
        if(a==inf || a>b)break;
    }
    return i;
}
inline void upd(int &x,int y){x>y?x=y:0;}
int main(){
    scanf("%d",&n);
    memset(pos,0x3f,sizeof(pos));
    memset(tr,0x3f,sizeof(tr));
    memset(f,0x3f,sizeof(f));
    for(int i=0,j,x;i<n;++i){
        j=0;
        while(scanf("%d",&x) && x){
            ht[i][j]=--x;
            pos[i][x]=j++;
            st[i]|=1<<x;
        }
        len[i]=j;
    }
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            if(i!=j)tr[i][j]=get_tr(i,j);
    f[0][n][0][n][0]=0;
    for(int i=0;i<n;++i)
        f[1<<i][i][len[i]][n][0]=0;
    ans=inf;
    for(int S=0;S<(1<<n);++S){
        for(int i=0;i<=n;++i){
            for(int l=len[i];~l;--l){
                for(int j=0;j<=n;++j){
                    for(int r=0;r<=len[j];++r){
                        if((cur=f[S][i][l][j][r])>=inf)continue;
                        if(S==(1<<n)-1 && l==0 && r==len[j])upd(ans,cur);
                        for(int k=0;k<n;++k){
                            if(S>>k&1)continue;
                            if(i!=n && l==0)
                                for(int x=tr[k][i];x<=len[k];++x)
                                    upd(f[S|(1<<k)][k][x][j][r],cur);
                            if(j==n || r>=tr[j][k])
                                upd(f[S|(1<<k)][i][l][k][0],cur);
                        }
                        if(i!=n && l==0)upd(f[S][n][0][j][r],cur);
                        for(int k=0,L,R;k<9;++k){
                            if(i==n)L=0;
                            else{
                                if(pos[i][k]>l)continue;
                                L=l-(pos[i][k]==l-1);
                            }
                            if(j==n)R=0;
                            else{
                                if(pos[j][k]>r)continue;
                                R=r+(pos[j][k]==r);
                            }
                            upd(f[S][i][L][j][R],cur+1);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n",ans<inf?ans:-1);
    return 0;
}