CF gym 101343 J Husam and the Broken Present 2

题目：Husam and the Broken Present 2

思路：
被其他串包含的串一定不会对答案造成影响，所以先把这些串去掉。
对于其他的串，可以预处理出两两之间的公共部分的长度，即第一个串的前缀和第二个串的后缀有多少公共部分。
令状态f[i][j]表示最后链接的是i串，其中j的串已被使用的最优结果。j是所有串是否被使用的01数组的二进制表示。
状态转移方程：
f[k][j|x]=min(f[k][j|x],f[i][j]+m[k]-g[i][k])
边界：
f[k][(1<<k-1)]=m[k]

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 15
#define maxm 100
#define maxs (1<<16)
#define inf (1<<30)int n;
int m[maxn+5]= {
   0};
vector<int> a[maxn+5];int g[maxn+5][maxn+5]= {
   0};
int f[maxn+5][maxs+5]= {
   0};void initf(int St) {for(int j=1; j<St; j++) {for(int i=1; i<=n; i++) {f[i][j]=(1<<30);}}for(int k=1; k<=n; k++) {f[k][(1<<k-1)]=m[k];}
}int dp() {int St=(1<<n);initf(St);for(int j=1; j<St; j++) {for(int i=1; i<=n; i++) {if(!((1<<i-1)&j)) continue;for(int k=1; k<=n; k++) {int x=(1<<k-1);if(!(j&x)) {f[k][j|x]=min(f[k][j|x],f[i][j]+m[k]-g[i][k]);}}}}int ans=inf;for(int i=1; i<=n; i++) {ans=min(f[i][(1<<n)-1],ans);}return ans;
}void readin() {scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d",&m[i]);for(int j=1; j<=m[i]; j++) {int x;scanf("%d",&x);a[i].push_back(x);}}
}int findprefix(int y,int x) {int ans=0;for(int i=0; i<m[x]; i++) {int s=0;for(int j=m[y]-i-1;j<m[y];j++) {if(a[x][s]!=a[y][j]) goto T;s++;}ans=max(ans,s);T:;}return ans;
}bool cnt[maxn+5]={
   0};bool findh(int x,int y) {for(int i=0;i<m[y]-m[x];i++) {for(int j=0;j<m[x];j++){if(a[x][j]!=a[y][i+j]) goto F;}return true;F:;}return false;
}void del(){for(int i=1;i<=n;i++) {if(!cnt[i]) continue;for(int j=i;j<=n;j++) {a[j]=a[j+1];cnt[j]=cnt[j+1];m[j]=m[j+1]; }n--,i--;}
}void init() {for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) {if(i==j||cnt[i]||cnt[j]) continue;if(m[i]>m[j]) continue;if(findh(i,j)) cnt[i]=1;}}del();for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++) {if(j==i) continue;else g[i][j]=findprefix(i,j);}}
}int main() {readin();init();int ans=dp();printf("%d",ans);return 0;
}