CodeForces 101343J (Husam and the Broken Present 2)[状压DP]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/gym/101343/problem/J

题意：构造一个序列包含所给的N个子序列(N≤15)，求构造序列的最短长度。
考虑状态压缩，有2^N种状态，设dp[i][j]表示状态为i，以第j个子序列结尾的最小长度；
状态转移：从以第j个子序列结尾的状态转移到以第k个子序列的状态：
dp[i|(1 << (k-1))][k] = min{dp[i][j]+a[k][0]-num[j][k]} （其中，a[k][0]表示第k个子序列的长度，num[j][k]表示第j个子序列的后缀与第k个子序列的前缀重合部分的长度）
注意：先将被其他子序列包含的子序列删去……
引用自GraceSkyer

感觉这题有包含的情况是个坑啊，另外需要注意的是两串相等的情况，可以把它们特判成两串不包含的情况。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int inf=0x3f3f3f3f;
int a[16][101];
bool cov[16];
int tot=0;
int pos[16];
int comm[16][16];
int dp[32769][16];
int main() {
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i][0]);
        for(int j=1;j<=a[i][0];j++) {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j || a[j][0]>a[i][0]) continue;
            for(int l=1;l+a[j][0]-1<=a[i][0];l++) {
                bool flag=true;
                for(int k=1;k<=a[j][0];k++)
                    if(a[i][l+k-1]!=a[j][k]) {
                        flag=false;
                        break;
                    }
                if(flag && !(a[i][0]==a[j][0] && l==1)) cov[j]=true; //特判两串相等的情况
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(!cov[i]) pos[++tot]=i;
    }
    for(int i=1;i<=tot;i++) {
        for(int j=1;j<=tot;j++) {
            if(i==j) { comm[i][i]=a[pos[i]][0];continue; }
            comm[i][j]=0;
            for(int l=1;l<=min(a[pos[i]][0],a[pos[j]][0]);l++) {
                bool flag=true;
                for(int k=1;k<=l;k++) {
                    if(a[pos[i]][a[pos[i]][0]-l+k]!=a[pos[j]][k]) {
                        flag=false;
                        break;
                    }
                }
                if(flag) comm[i][j]=l;
            }
        }
    }
    int mx=(1<<tot);
    for(int i=0;i<mx;i++)
        for(int j=0;j<=tot;j++)
            dp[i][j]=inf;
    //dp[0][0]=0;
    for(int j=1;j<=tot;j++) {
        dp[1<<(j-1)][j]=a[pos[j]][0];
    }
    for(int i=0;i<mx;i++) {
        for(int j=1;j<=tot;j++) {
            if(!(i&(1<<(j-1)))) continue;
            for(int k=1;k<=tot;k++) {
                if(j==k) continue;
                dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+a[pos[k]][0]-comm[j][k]);
            }
        }
    }
    int ans=inf;
    for(int i=1;i<=tot;i++)
        ans=min(ans,dp[mx-1][i]);
    printf("%d",ans);
}