洛谷P1019 单词接龙

预处理单词i连接单词j的最小重叠部分,然后dfs即可.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int ex[25][25];
string s[25];
int n;
void pre() {
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      int len1 = s[i].length();
      int len2 = s[j].length();
      for (int k = 1; k <= len1 - 1; ++k) {
        int m = 0;
        for (; m < len2 - 1 && m < k; ++m) {
          if (s[i][len1 - k + m] != s[j][m]) {
            break;
          }
        }
        if (m == k && m < len2 - 1) {
          ex[i][j] = k;
          break;
        }
      }
    }
  }
}
int vis[25];
int ans;

void dfs(int i, int len) {
  vis[i]++;
  // cout<<i<<endl;
  int j = 0;
  for (j = 0; j < n; ++j) {
    if (ex[i][j] && vis[j] < 2) {
      dfs(j, len + s[j].length() - ex[i][j]);
      vis[j]--;
    }
  }
  if (j == n) ans = max(ans, len);
}

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> s[i];
  }
  char a;
  cin >> a;
  pre();
  for (int i = 0; i < n; ++i) {
    if (s[i][0] == a) {
      dfs(i, s[i].length());
      vis[i]--;
    }
  }
  cout << ans << endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}