正題

luogu 1019

---

題目大意

給你若干個詞語，讓你把他們連起來（重復段疊在一起），每個詞語最多用兩次，問你該串最長是多少

---

解題思路

dfs枚舉一個單詞后面接哪個單詞，然后枚舉重疊長度，再用hash判斷是否相同

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 200 using namespace std; int n, ans, l[N], p[N]; unsigned long long pw[N], hs[N][N]; char s[N][N]; void dfs(int x, int sum) {ans = max(ans, sum);for (int i = 1; i <=n; ++i){if (p[i] == 2) continue;int g = 0;for (int len = 1; len <= min(l[x], l[i]) - 1; ++len){int j = l[x] - len;if (hs[x][l[x]] - hs[x][j] * pw[len] == hs[i][len])//判斷是否相等{g = len;//最短的長度break;}}if (g){p[i]++;//記錄使用次數dfs(i, sum + l[i] - g);p[i]--;}}return; } int main() {scanf("%d", &n);pw[0] = 1;for (int i = 1; i <= 1000; ++i)pw[i] = pw[i - 1] * 131;for (int i = 1; i <= n; ++i){scanf("%s", s[i]+1); l[i] = strlen(s[i]+1);hs[i][0] = 0;for (int j = 1; j <= l[i]; ++j)hs[i][j] = hs[i][j - 1] * 131 + s[i][j];}scanf("%s", s[0]+2);s[0][1] = '/';l[0] = strlen(s[0]+1);hs[0][0] = 0;for (int j = 1; j <= l[0]; ++j)hs[0][j] = hs[0][j - 1] * 131 + s[0][j];dfs(0, 1);printf("%d", ans);return 0; }

總結

以上是生活随笔為你收集整理的【dfs】【hash】有趣的英语角（2015特长生 T2/luogu 1019）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。