关于此题[ABC343G] Compress Strings 状压DP的一些总结

传送门

• 通过这道题也是让我对TSP问题有了更深的理解。
• 首先这道题中给定n个字符串，我们发现n的范围只有20。让我们求这n个字符串作为同一个字符串的子串时，该字符串最短是多少。
• 我们发现，如果有一个字符串被另一个字符串完全包含，那么它对答案是没有影响的，所以我们可以先用哈希标记掉这些字符串。接下来的问题就是，对于两个字符串\(s_{i}\)和\(s_{j}\)，我们令\(trans[i][j]\)表示\(s_{j}\)接到\(s_{i}\)后需要新增的长度。我们可以预处理出所有的\(trans[i][j]\)，那么接下来问题就变成了，我们需要所有的字符串都被包含需要的最小的“代价”。再说的更直白一些，假定每个字符串是一个节点，这n个节点组成一个完全图，而每个\(i\)节点到\(j\)节点的路径权值就是\(trans[i][j]\)，问经过所有节点所需要的最小代价是多少，于是这道题就被转化成了TSP问题，用状压DP来解决。

#include<bits/stdc++.h>
    
using namespace std;
    
const int b = 233;
int t;
const int N = 2e5 + 10;
int n,trans[21][21],f[21][1050000];
string s[21];
unsigned long long h[21][N],p[N];
bool v[21];
    
void solve() {
    memset(f,0x3f,sizeof f);
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> s[i];
        for(int j = 0;j < s[i].length();j++)
            h[i][j + 1] = h[i][j] * b + s[i][j];
    }
    p[0] = 1;
    for(int i = 1;i < N;i++) p[i] = p[i-1] * b;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            if(j == i || v[j]) continue;
            if(s[i].length() > s[j].length()) continue;
            for(int k = 0;k < s[j].length();k++) {
                if(k + s[i].length() > s[j].length()) break;
                if(h[i][s[i].length()] == h[j][k + s[i].length()] - h[j][k] * p[s[i].length()]) {
                    v[i] = 1;
                    break;
                }
            }
        }
    }
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            if(i == j || v[i] || v[j]) continue;
            trans[i][j] = s[j].length();
            for(int k = 0;k < s[j].length();k++) {
                if(h[j][k + 1] == h[i][s[i].length()] - h[i][s[i].length() - k - 1] * p[k + 1]) {
                    trans[i][j] = s[j].length() - k - 1;
                }
            }
        }
    }

    for(int i = 1;i <= n;i++)
        f[i][1 << (i - 1)] = s[i].length();

    for(int i = 1;i < (1 << n);i++) {
        for(int j = 1;j <= n;j++) {
            if(v[j]) continue;
            if(i & (1 << (j - 1))) {
                for(int k = 1;k <= n;k++) {
                    if(k == j || v[k]) continue;
                    if(i & (1 << (k - 1))) f[j][i] = min(f[j][i],f[k][i ^ (1 << (j - 1))] + trans[k][j]);
                }
            }   
        }
    }

    int ans = 1e8,tmp = (1 << n) - 1;
    for(int i = 1;i <= n;i++) if(v[i]) tmp ^= (1 << (i - 1));
    for(int i = 1;i <= n;i++)
        ans = min(ans,f[i][tmp]);
    cout << ans;
}
    
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    t = 1;
    while(t--) solve();
    
    return 0;
}