gym101343J. Husam and the Broken Present 2 (状压DP)

题意:给定n个串每个串长度不超过100

　　找到一个新串使得这n个串都是它的字串输出这个新串的最小长度

题解:n是15 n的阶乘的复杂度肯定不行就想到了2的15次方的复杂度

　　想到了状压但是不知道怎么维护所以加一维就好了 dp[i][j]表示当前状态为i 且末尾是第j个串

转移简直弱智预处理val[i][j]表示第i个串和第j个串拼在一起会节省的长度那么答案最后就是总长度减去节省最大的长度了

　　然后还要注意一下包含的问题假如1 2 3，2 3 4 5和3 4这三个串3 4是被包含的

　　但是你转移的时候1 2 3和2 3 4 5接在一起后变成 1 2 3 4 5包含了3 4但是此时的状态还是只用了第1个和第2个串的状态

　　所以把包含的串去重一下就好了... 弱智这都写了四个小时

#include <bits/stdc++.h>
using namespace std;

int vis[20];
int num[20];
int q[20][105];
int val[20][20];
int dp[70000][20];

int main()
{
    int n;
    scanf("%d", &n);

    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &q[i][0]);
        for(int j = 1; j <= q[i][0]; j++) scanf("%d", &q[i][j]);
    }
    for(int i = 1; i <= n; i++) vis[i] = 1;

    int cnt = 0;
    for(int i = 1; i <= n; i++)                //去重
    {
        if(!vis[i]) continue;
        for(int j = 1; j <= n; j++)
        {
            if(i == j) continue;
            if(!vis[j]) continue;

            if(q[i][0] >= q[j][0])
            {
                for(int k = 1; k + q[j][0] - 1 <= q[i][0]; k++)
                {
                    bool f = true;
                    for(int kk = 1; kk <= q[j][0]; kk++)
                    {
                        if(q[i][k + kk - 1] == q[j][kk]) continue;
                        else {f = false; break;}
                    }
                    if(f) {vis[j] = 0; break;}
                }
            }
        }
    }

    for(int i = 1; i <= n; i++) if(vis[i]) cnt++;

    int zn = 0;
    for(int i = 1; i <= n; i++) if(vis[i]) num[++zn] = i;

    for(int i = 1; i <= zn; i++)
    {
        for(int j = 0; j <= q[num[i]][0]; j++) q[i][j] = q[num[i]][j];
        ans += q[i][0];
    }

    for(int i = 1; i <= cnt; i++)          //预处理价值
    {
        for(int j = 1; j <= cnt; j++)
        {
            if(i == j) continue;
            val[i][j] = 0;
            for(int k = 1; k <= q[i][0]; k++)
            {
                if(q[i][k] == q[j][1])
                {
                    bool f  = true;
                    for(int kk = 1; kk + k <= q[i][0]; kk++)
                    {
                        if(q[i][k + kk] == q[j][kk + 1]) continue;
                        else { f = false; break;}
                    }
                    if(f) {val[i][j] = q[i][0] - k + 1; break;}
                }
            }
        }
    }
    memset(dp, 0, sizeof(dp));

    int sta = (1 << cnt) - 1;
    for(int i = 0; i <= sta; i++)
    {
        memset(vis, 0, sizeof(vis));
        for(int j = 0; j < n; j++)
        {
            int c = (i >> j) & 1;
            if(c == 1) vis[j + 1] = 1;
        }

        for(int j = 1; j <= n; j++)
        {
            if(vis[j]) continue;
            int v = (1 << (j - 1));

            for(int k = 1; k <= n; k++)
            {
                if(!vis[k]) continue;
                dp[i + v][j] = max(dp[i + v][j], dp[i][k] + val[k][j]);
            }
        }
    }

    int zd = 0;
    for(int i = 1; i <= cnt; i++) zd = max(zd, dp[sta][i]);
    printf("%d
", ans - zd);
    return 0;
}

/*
3
3 1 2 3
2 3 4
4 2 3 4 5
*/

View Code