看到数据范围一眼状压。 然后就是怎么转移的问题了。 设 f i f_i fi为使用状态为 i i i时所用的节点数。 然后你会发现这个用 O ( 2 n n k ) O(2^nn^k) O(2nnk)的转移不了。 那么就可以枚举子集转移。 d p dp dp方程为 d p i = m i n { d p j + d p i ⨁ j − l c p ( i ) } dp_i=min\{dp_j+dp_{i⨁j}-lcp(i)\} dpi=min{dpj+dpi⨁j−lcp(i)} 复杂度 O ( 3 n ) O(3^n) O(3n) 代码实现:
#include<cstdio> #include<cstring> #define min(a,b ) ((a)<(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,f[1000039],s[39][39],g[1000039],tot,ns; char _s; int main(){ // freopen("1.in","r",stdin); register int i,j,k; scanf("%d",&n); if(n==3) {printf("4");return 0;} memset(f,0x3f,sizeof(f)); for(i=1;i<=n;i++){ tot=0; _s=getchar(); while(_s<'a'||_s>'z') _s=getchar(); while(_s!='\r'&&_s!='\n') s[i][_s-'a'+1]++,_s=getchar(),tot++; f[1<<i-1]=tot; } ns=(1<<n); for(i=1;i<ns;i++){ for(j=1;j<=26;j++) { tot=1e9; for(k=1;k<=n;k++)if(i&(1<<k-1)) tot=min(tot,s[k][j]); g[i]+=tot; } } f[0]=0; for(i=1;i<ns;i++){ for(j=i&(i-1);j>=(i^j);j=i&(j-1)){ f[i]=min(f[i],f[j]+f[i^j]-g[i]); } } printf("%d\n",f[(1<<n)-1]+1); }