题解

要求复杂度在内，很显然这样的复杂度应该是用状压dp。

令表示已经放了的状态下，最后放入的是第个字符串的最小答案。（这里的下标从开始）

那么就有这样的状态转移：

首先如果状态中只有一个字符串，那么。（表示第个字符串的长度）

那么对于状态中不止有一个字符串的，且有的有：

这里表示的意思是当前是要放第个字符串，然后上一个字符串是第个字符串，然后转移。其中的意思是前面先放第字符串后面放字符串所能缩短的最多字符大小。

状压dp部分的复杂度就已经到达了，如果再在里面再求tmp数组的话复杂度会很高。

很显然需要预处理tmp数组。如何去预处理呢？

最暴力的方式就是直接枚举前缀后缀进行比较，但是这样的话复杂度会到达，不能达到预期。

可以想到字符串的一些方法来优化的部分把它优化成，例如后缀数组、后缀自动机、z_function之类的算法。

我是用的是z_function，写起来比较短，而且很好用。

z_function是输入一个长度为的字符串然后处理出第个位置的后缀与的前缀的最长公共前缀长度。

于是把用一个字符串str2 + "*"(一个未出现过的字符) + str1扔进z_function得到z数组，那么对于的部分中，如果就表示这个可以作为两个字符串重叠的部分。枚举两个字符串后做到了处理。即总的预处理字符串的复杂度是。

那么预处理加上状压dp的复杂度是达到了预期。

代码

#include<bits/stdc++.h>
using namespace std;
string str[11];
int dp[1 << 11][11];
int tmp[11][11];
vector<int> z_function(string s) {
  int n = (int)s.length();
  vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; i++) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
int main() {
  int T; cin >> T;
  while(T--) {
    int n, l; cin >> n >> l;
    for(int i = 0; i < n; i++) {
      cin >> str[i];
    }
    // 预处理tmp数组
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        tmp[i][j] = 0;
        string nw = str[j] + "$" + str[i];
        vector<int> z = z_function(nw);
        const int sz = nw.size();
        for(int k = int(str[j].size()) + 1; k < sz; k++) {
          if(sz - k == z[k]) {
            tmp[i][j] = z[k];
            break;
          }
        }
      }
    }
    // 置为最大值
    for(int i = 0; i < (1 << n); i++) {
      for(int j = 0; j < n; j++) {
        dp[i][j] = 0x3f3f3f3f;
      }
    }
    // dp初始值
    for(int i = 0; i < n; i++) {
      dp[1 << i][i] = str[i].size();
    }
    // 状压dp
    for(int i = 0; i < (1 << n); i++) {
      const int cur = __builtin_popcount(i);
      if(cur == 1) continue;
      for(int j = 0; j < n; j++) {
        if((i >> j) & 1) {
          for(int k = 0; k < n; k++) {
            dp[i][j] = min(dp[i][j], dp[i ^ (1 << j)][k] + int(str[j].size()) - tmp[k][j]);
          }
        }
      }
    }
    int mn = INT_MAX;
    for(int i = 0; i < n; i++) {
      mn = min(mn, dp[(1 << n) - 1][i]);
    }
    cout << mn << '\n';
  }
}