题目描述
Bessie is playing a video game! In the game, the three letters &＃39;A&＃39;, &＃39;B&＃39;, and &＃39;C&＃39; are the only valid buttons. Bessie may press the buttons in any order she likes; however, there are only N distinct combos possible (1 <= N <= 20). Combo i is represented as a string S_i which has a length between 1 and 15 and contains only the letters &＃39;A&＃39;, &＃39;B&＃39;, and &＃39;C&＃39;.
Whenever Bessie presses a combination of letters that matches with a combo, she gets one point for the combo. Combos may overlap with each other or even finish at the same time! For example if N = 3 and the three possible combos are "ABA", "CB", and "ABACB", and Bessie presses "ABACB", she will end with 3 points. Bessie may score points for a single combo more than once.
Bessie of course wants to earn points as quickly as possible. If she presses exactly K buttons (1 <= K <= 1,000), what is the maximum number of points she can earn?
贝西在玩一款游戏，该游戏只有三个技能键 “A”“B”“C”可用，但这些键可用形成N种(1 <= N<= 20)特定的组合技。第i个组合技用一个长度为1到15的字符串S_i表示。
当贝西输入的一个字符序列和一个组合技匹配的时候，他将获得1分。特殊的，他输入的一个字符序列有可能同时和若干个组合技匹配，比如N=3时，3种组合技分别为"ABA", "CB", 和"ABACB",若贝西输入"ABACB"，他将获得3分。
若贝西输入恰好K (1 <= K <= 1,000)个字符，他最多能获得多少分？
输入输出格式
输入格式：-
Line 1: Two space-separated integers: N and K.
- Lines 2..N+1: Line i+1 contains only the string S_i, representing combo i.
- Line 1: A single integer, the maximum number of points Bessie can obtain.
输入输出样例
3 7
ABA
CB
ABACB
4
说明
The optimal sequence of buttons in this case is ABACBCB, which gives 4 points--1 from ABA, 1 from ABACB, and 2 from CB.
题解：
记cnt[i]为节点i沿着fail一直走下去可以获得的积分,那么
f[i][j]为走了i步到节点j的最大积分 注意初始化...
f[i][a[j].next[k]]=max(f[i][a[j].next[k]],f[i-1][j]+a[a[j].next[k]].cnt);
1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7 const int INF=-2e8;
8 struct node
9 {
10 int next[3];
11 int cnt;
12 }a[505];
13 int f[1005][505];
14 int root=0,num=0,fail[505];
15 char s[1005];
16 void Clear()
17 {
18 a[num].cnt=0;
19 for(int i=0;i<3;i++)a[num].next[i]=0;
20 }
21 void add()
22 {
23 scanf("%s",s);
24 int p=root;
25 for(int i=0,ls=strlen(s);i
26 {
27 if(a[p].next[s[i]-&＃39;A&＃39;])p=a[p].next[s[i]-&＃39;A&＃39;];
28 else
29 {
30 a[p].next[s[i]-&＃39;A&＃39;]=++num;
31 Clear();
32 p=num;
33 }
34 }
35 a[p].cnt++;
36 }
37 void getfail()
38 {
39 queue<int>q;
40 q.push(root);
41 int u,p,v;
42 while(!q.empty())
43 {
44 u=q.front();q.pop();
45 for(int i=0;i<3;i++)
46 {
47 if(!a[u].next[i])
48 {
49 if(a[fail[u]].next[i])a[u].next[i]=a[fail[u]].next[i];
50 continue;
51 }
52 p=fail[u];
53 while(p)
54 {
55 if(a[p].next[i])break;
56 p=fail[p];
57 }
58 if(a[p].next[i] && a[p].next[i]!=a[u].next[i])fail[a[u].next[i]]=a[p].next[i];
59 v=a[u].next[i];
60 a[v].cnt+=a[fail[v]].cnt;
61 q.push(a[u].next[i]);
62 }
63 }
64 }
65 int main()
66 {
67 //freopen("pp.in","r",stdin);
68 int n,k,ans=0;
69 scanf("%d%d",&n,&k);
70 for(int i=1;i<=n;i++)
71 add();
72 getfail();
73 for(int i=0;i<=k;i++)
74 for(int j=0;j<=num;j++)
75 f[i][j]=INF;
76 f[0][0]=0;
77 for(int i=1;i<=k;i++)
78 {
79 for(int j=0;j<=num;j++)
80 {
81 for(int k=0;k<3;k++)
82 {
83 f[i][a[j].next[k]]=max(f[i][a[j].next[k]],f[i-1][j]+a[a[j].next[k]].cnt);
84 }
85 }
86 }
87 for(int i=1;i<=num;i++)if(f[k][i]>ans)ans=f[k][i];
88 printf("%d\n",ans);
89 return 0;
90 }
京公网安备 11010802041100号