CERC2016 I, Invisible Integers

题目大意

对一个包含若干 $1$ 到 $9$ 之间的整数的序列,我们可以用以下方法生成若干条提示:

  1. 随机选择序列中的一个位置作为起点。
  2. 随机选择一个方向(左/右)。
  3. 从起点开始沿着选定的方向走,遍历完这个方向的每个数字,将每个数字第一次出现的顺序记录下来。

现在给定 $n$ 条提示,请找到长度最短的满足条件的整数序列。

$1\leq n\leq 10$


题目分析

不妨先考虑假如所有的提示都是从左向右的怎么做。
首先不难发现,提示 $y$ 能比提示 $x$ 晚出现,当且仅当 $y$ 中所有数都在 $x$ 中出现。
考虑从左往右匹配的过程,可以观察到提示之间可能存在类似“转化”的关系。
定义提示 $x$ 在第 $i$ 位之后可以转化成提示 $y$,当且仅当:

  1. 到目前为止,提示 $x$ 前 $i$ 位数字都已经被匹配了。
  2. 提示 $y$ 能比提示 $x$ 晚出现。
  3. 提示 $x$ 第 $i$ 位后面的数字,在提示 $y$ 中出现的相对顺序不变。

可以观察到,如果提示 $x$ 在第 $i$ 位之后可以转化成提示 $y$,那么后面我们继续填数时就可以忽略掉提示 $x$ 是否被满足,因为在这时提示 $x$ 被满足的条件已经严格弱于提示 $y$ 被满足的条件。

有了这个思路,我们可以得到一个顺序的 $dp$ 算法,令 $f_{s,x,i}$ 表示当前所有被转化过的提示集合为 $s$、当前最后转化到提示编号为 $x$、这个提示匹配到的位置为 $i$ 的状态下,序列长度的最小值。
每次我们枚举最后一维新加入的数字,显然这个数字要么是匹配的下一位,要么是当前提示前 $i$ 位数字中的一个。

接下来考虑从右向左的提示,可以发现我们只需要在原来基础上加多两维,分别记录当前从右向左的提示最后转移到了提示 $y$,这个提示匹配到的位置 $j$(从右向左)。转移依然是和只考虑一种方向时候的类似的。

时间复杂度 $O\left(2^n\times (dn)^2\times (n+d)\right)$。


代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}

const int N=10;
const int S=1<<N;
const int D=9;
const int INF=N*D+100;

bool transition[N+1][D+1][N+1];
int f[S][N+1][D+1][N+1][D+1];
int exist[N+1][D+1];
int hint[N+1][D];
int len[N+1];
int n,ans;

inline bool transitive(int x,int p,int y)
{
if (~exist[x][len[x]]&(y==n?0:exist[y][len[y]])) return 0;
for (int i=0;i<len[y]&&p<len[x];++i) p+=hint[x][p]==hint[y][i];
return p==len[x];
}

inline int min(int x,int y){return x<y?x:y;}

int dp(int s,int l,int curl,int r,int curr)
{
if (s==(1<<n)-1&&!curl&&curr==len[r]) return 0;
if (~f[s][l][curl][r][curr]) return f[s][l][curl][r][curr];
int ret=INF;
if (l<n&&!curl)
for (int l_=0;l_<=n;++l_)
if (s>>l_&1^1)
for (int curl_=0;curl_<=len[l_];++curl_)
if (transition[l_][curl_][l])
ret=min(ret,dp(l_==n?s:s|1<<l_,l_,curl_,r,curr));
for (int r_=0;r_<n;++r_)
if ((s>>r_&1^1)&&transition[r][curr][r_])
ret=min(ret,dp(s|1<<r_,l,curl,r_,0));
for (int d=1;d<=D;++d)
{
if (curl&&curr<len[r]&&hint[l][curl-1]==d&&hint[r][curr]==d) ret=min(ret,dp(s,l,curl-1,r,curr+1)+1);
if (curl&&hint[l][curl-1]==d&&(exist[r][curr]>>d&1)) ret=min(ret,dp(s,l,curl-1,r,curr)+1);
if (curr<len[r]&&hint[r][curr]==d&&(exist[l][curl]>>d&1)) ret=min(ret,dp(s,l,curl,r,curr+1)+1);
}
return f[s][l][curl][r][curr]=ret;
}

int main()
{
freopen("invint.in","r",stdin),freopen("invint.out","w",stdout);
n=read();
for (int i=0;i<n;++i)
for (int x;x=read();)
hint[i][len[i]++]=x;
len[n]=0;
for (int i=0;i<=n;++i)
for (int j=0;j<=len[i];++j)
if (i==n) exist[i][j]=(1<<D+1)-1;
else exist[i][j]=(j?exist[i][j-1]|1<<hint[i][j-1]:0);
for (int i=0;i<=n;++i)
for (int j=0;j<=len[i];++j)
for (int k=0;k<=n;++k)
if (i!=k) transition[i][j][k]=i==n||transitive(i,j,k);
ans=INF,memset(f,-1,sizeof f);
for (int i=0;i<=n;++i) ans=min(ans,dp(i==n?0:1<<i,i,len[i],n,0));
printf("%d\n",ans==INF?-1:ans);
fclose(stdin),fclose(stdout);
return 0;
}