猜数列
有一个长度为(m)的，由(1)到(9)之间的数构成的未知数列(a)。
你现在有(n)个线索，每个线索都是用如下方式生成的：
-
选择序列(a)的某一个位置(p)作为开始。
-
选择某个方向（向左或向右）。
-
从(p)出发往你选择的方向走，每遇到一个之前未出现的数就将它加到线索中。
（可以发现，每条线索的长度都不超过(9)。）
现在你需要求出满足所有线索的长度最小的序列的长度。
对于(100\%)的数据，(1leq n leq 10)。
题解
https://www.cnblogs.com/yyf0309/p/10124870.html
依次从左到右考虑每一位上填的数。
设(F[l][x][r][y][S])表示正在匹配往左走的线索(l)的第(x)位，正在匹配向右走的线索(r)的第(y)位，已经考虑过的线索集合是(S)的最小代价。
-
往左走的线索已经匹配上了(nsim x+1)。当(x=0)时说明已经完全匹配了。
-
往右走的线索已经匹配上了(1sim y-1)。当(y= ext{len}_r+1)时说明已经完全匹配了。
主要有两种转移：
-
填下一个字符
如果两个线索正在匹配的字符相同，那么直接填。如果不同则还需判断一下是否会使得另一线索不满足条件。
-
如果当前选择的字符没有匹配上往左走的下一个，那么往左走的线索需要满足(xsim 1)中出现了这个字符。
-
如果当前选择的字符没有匹配上往右走的下一个，那么往右走的线索需要满足(1sim y-1)中出现了这个字符。
-
-
更换线索
-
更换向左走的线索需要满足原线索的前缀能匹配新线索的后缀
大概就是说当(l={1,2,3,4,5},x=3,l'={1,2,3})的时候，可以由(F[l][3][S])转移到(F[l'][3][S])。
但是注意到这个形式，我们一定可以在(x=0)的时候更换向左走的线索。
-
更换向右走的线索需要满足原线索的后缀能匹配新线索的前缀。
大概就是说当(r={1,2,3,4,5},x=3,r'={3,4,5})的时候，可以由(F[r][3][S])转移到(F[r'][1][S])。
能不能在某个串的某个位置处更换某个串可以预处理出来。
-
时间复杂度(O(2^ncdot n^3cdot 10^2))。
int n;
int a[11][12],len[11];
int b[11][12],go[11][11][11];
bool check(int x,int y,int z){ // x matching position y
if(b[z][len[z]]&~b[x][len[x]]) return 0; // z has something x doesn't have
for(int i=1;i<=len[z];++i)if(a[z][i]==a[x][y]) ++y;
return y==len[x]+1;
}
int F[11][11][11][12][1<<10];
int solve(int l,int x,int r,int y,int mask){
int&ans=F[l][x][r][y][mask&=bin(n)];
if(ans!=-1) return ans;
if(mask==bin(n) and x==0 and y==len[r]+1) return ans=0; // able to end
ans=1e9;
if(l<n and x==0){
for(int i=0;i<=n;++i)if(~mask>>i&1)
for(int j=1;j<=len[i]+1;++j)if(go[i][j][l])
ans=min(ans,solve(i,j-1,r,y,mask|1<<i));
}
else{
for(int i=0;i<n;++i)if(~mask>>i&1)
if(go[r][y][i]) ans=min(ans,solve(l,x,i,1,mask|1<<i));
for(int i=1;i<=9;++i){
bool u=i==a[l][x],v=i==a[r][y];
if(u and v) ans=min(ans,solve(l,x-1,r,y+1,mask)+1);
if(u and b[r][y-1]>>i&1) ans=min(ans,solve(l,x-1,r,y,mask)+1);
if(v and b[l][x]>>i&1) ans=min(ans,solve(l,x,r,y+1,mask)+1);
}
}
return ans;
}
int main(){
read(n);
for(int i=0;i<n;++i){
for(int x;read(x);) a[i][++len[i]]=x;
for(int j=1;j<=len[i];++j) b[i][j]=b[i][j-1]|1<<a[i][j];
}
b[n][0]=~0; // n can concatenate everything
for(int i=0;i<=n;++i)for(int j=1;j<=len[i]+1;++j)
for(int k=0;k<=n;++k)if(k!=i)
go[i][j][k]=check(i,j,k);
memset(F,-1,sizeof F);
int ans=1e9;
for(int i=0;i<=n;++i)
ans=min(ans,solve(i,len[i],n,1,1<<i));
printf("%d
",ans==1e9?-1:ans);
return 0;
}