看数据可以猜测：这是一道状态压缩的动态规划题
没错。
我们用
f
i
f_i
fi 表示在
i
i
i 状态下最少需要多少节点。
那么转移方程就是：
f
i
=
min
j
&
i
=
j
f
j
+
f
i
−
j
−
l
c
p
(
i
)
f_i=\min\limits_{j\&i=j}{f_j+f_{i-j}-lcp(i)}
fi=j&i=jminfj+fi−j−lcp(i)
这个
l
c
p
(
i
)
lcp(i)
lcp(i) 就是在
i
i
i 状态下，每一个字符串的最长公共的前缀（只要能并到一起就并到一起）
最后，枚举子集的东西可以到网上搜一下
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
int n
;
char c
[1000001];
int s
[17][26];
int f
[1<<16],k
[1<<16];
int lcp(int x
){
memset(s
[n
],0x3f,sizeof(s
[n
]));
for(int i
=0;i
<n
;i
++){
if(x
>>i
&1){
for(int j
=0;j
<26;j
++){
if(s
[n
][j
]>s
[i
][j
])s
[n
][j
]=s
[i
][j
];
}
}
}
int ans
=0;
for(int i
=0;i
<26;i
++)ans
+=s
[n
][i
];
return ans
;
}
int main(){
scanf("%d",&n
);
memset(f
,0x3f,sizeof(f
));
for(int i
=0;i
<n
;i
++){
scanf("%s",c
);
int len
=0;
for(int j
=0;c
[j
];j
++){
s
[i
][c
[j
]-'a']++;
len
++;
}
f
[1<<i
]=len
;
}
for(int i
=1;i
<(1<<n
);i
++){
k
[i
]=lcp(i
);
}
for(int i
=1;i
<(1<<n
);i
++){
for(int j
=i
&(i
-1);j
>0;j
=(i
&(j
-1))){
f
[i
]=min(f
[i
],f
[j
]+f
[i
-j
]-k
[i
]);
}
}
printf("%d",f
[(1<<n
)-1]+1);
return 0;
}
