洛谷P1019 單詞接龍

題目描述

單詞接龍是一個與我們經常玩的成語接龍相類似的游戲，現在我們已知一組單詞，且給定一個開頭的字母，要求出以這個字母開頭的最長的“龍”（每個單詞都最多在“龍”中出現兩次），在兩個單詞相連時，其重合部分合為一部分，例如

輸入輸出格式

輸入格式：

輸入的第一行為一個單獨的整數 $\le 20n≤20)表示單詞數，以下nnn 行每行有一個單詞，輸入的最后一行為一個單個字符，表示“龍”開頭的字母。你可以假定以此字母開頭的“龍”一定存在.$

輸出格式：

只需輸出以此字母開頭的最長的“龍”的長度

本題我本來打算在深搜的時候在處理兩個單詞的相交部分，但發現預處理一下會更好

要注意使用string變量求其長度與char變量求長度有所不同；

string a;? int length=a.size(); ? ? //注意此處不是size(a)，一開始我在VScode上編譯竟沒報錯，然后提交洛谷評測，成功CE。。。

char a;? int length=strlen(a);

代碼如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<string> 
 7 using namespace std;
 8 #define maxn 1010
 9 #define ll long long
10 #define IL inline
11 #define clear(a) memset(a,0,sizeof a)
12 IL void read(int &x)
13 {
14     x = 0;int f = 1;char ch = getchar();
15     while(ch<'0'||ch>'9'){if(ch=='-')f = -f;ch = getchar();}
16     while(ch>='0'&&ch<='9'){x = x * 10 + ch - '0', ch = getchar();}x *= f;
17 }
18 
19 int n, ans;
20 char head;
21 int color[maxn], used[maxn];
22 int contact[maxn][maxn];
23 string z[maxn];
24 
25 void solve(int x,int y)
26 {
27     for (int i = 1; i <= min(z[x].size(), z[y].size()) - 1; i++)
28     {
29         int lazy = 0;
30         int pry = 0;
31         for (int j = z[x].size() - i; j <= z[x].size() - 1;j++)
32         {
33             if(z[x][j]==z[y][pry])
34                 pry++;
35             else
36             {
37                 lazy = 1;
38                 break;
39             }
40         }
41         if(lazy)
42             continue;
43         else
44         {
45             contact[x][y] = i;
46             break;
47         }
48     }
49 }
50 
51 void dfs(int id,int length)
52 {
53     ans = max(ans, length);
54     for (int i = 1; i <= n;i++)
55     {
56         if(color[i]>=2)
57             continue;
58         if(contact[id][i])
59         {
60             color[i]++;
61             dfs(i, length+z[i].size()-contact[id][i]);
62             color[i]--;
63         }
64     }
65     ans = max(ans, length);
66 }
67 
68 int main()
69 {
70     read(n);
71     for (int i = 1; i <= n;i++)
72         cin >> z[i];
73     cin >> head;
74     for (int i = 1; i <= n;i++)
75         for (int j = 1; j <= n;j++)
76             solve(i, j);
77     for (int i = 1; i <= n; i++)
78         if (z[i][0] == head)
79         {
80             color[i] = 1;
81             dfs(i, z[i].size());
82             color[i] = 0;
83         }
84     cout << ans;
85     return 0;
86 }

轉載于:https://www.cnblogs.com/KGW-/p/10367997.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/278333.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/278333.shtml
英文地址，請注明出處：http://en.pswp.cn/news/278333.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！