• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

【BZOJ】1830: [AHOI2008]Y型项链

admin

11月 28, 2021

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1830


直接枚举目标串是什么,目标串一定是三个字符串的某一个前缀(注意可能为空),然后判断一下取个最小值。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 55
10 #define llg long long 
11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
12 llg n,m,tot,ans,len,l[maxn];
13 
14 char s[5][maxn],aim[maxn];
15 
16 llg work(llg x)
17 {
18     llg wz=0;
19     for (llg i=1;i<=len;i++) 
20         if (aim[i]==s[x][i])
21         {
22             wz=i;
23         }
24         else break;
25     if (wz==len) return l[x]-len;
26     return (l[x]-wz)+len-wz;
27 }
28 
29 int main()
30 {
31     yyj("bzoj1830");
32     for (llg i=1;i<=3;i++)
33     {
34         cin>>l[i];
35         cin>>(s[i]+1);
36     }
37     ans=0x7fffffff;
38     for (llg k=1;k<=3;k++)
39         for (llg i=1;i<=1;i++)
40             for (llg j=i-1;j<=l[k];j++)
41             {
42                 for (llg w=0;w<maxn;w++) aim[w]='';
43                 tot=0;
44                 len=j-i+1;
45                 for (llg w=1;w<=len;w++) aim[w]=s[k][i+w-1];
46                 for (llg w=1;w<=3;w++) tot+=work(w);
47                 ans=min(ans,tot);
48             }
49     cout<<ans;
50     return 0;
51 }

发表回复

您的电子邮箱地址不会被公开。