描述
貝西在玩一款游戲，該游戲只有三個技能鍵 “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.
每次暴力枚舉下一個字符填什么在acacac自動機上dp就完了
注意下傳endendend
#include<bits/stdc++.h>
using namespace std
;
#define gc getchar
inline int read(){char ch
=gc();int res
=0,f
=1;while(!isdigit(ch
))f
^=ch
=='-',ch
=gc();while(isdigit(ch
))res
=(res
+(res
<<2)<<1)+(ch
^48),ch
=gc();return f
?res
:-res
;
}
#define pb push_back
#define re register
#define cs const
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
inline void chemx(int &a
,int b
){a
<b
?a
=b
:0;
}
inline void chemn(int &a
,int b
){a
>b
?a
=b
:0;
}
const int N
=305;
namespace Ac
{int nxt
[N
][3],fail
[N
],end
[N
],tot
;inline void insert(char *s
){int p
=0;for(int i
=1,len
=strlen(s
+1);i
<=len
;i
++){int c
=s
[i
]-'A';if(!nxt
[p
][c
])nxt
[p
][c
]=++tot
;p
=nxt
[p
][c
];}end
[p
]++;}queue
<int> q
;inline void build(){for(int i
=0;i
<3;i
++){int v
=nxt
[0][i
];if(v
)q
.push(v
),fail
[v
]=0;}while(!q
.empty()){int p
=q
.front();q
.pop();for(int c
=0;c
<3;c
++){int v
=nxt
[p
][c
];if(!v
)nxt
[p
][c
]=nxt
[fail
[p
]][c
];else fail
[v
]=nxt
[fail
[p
]][c
],q
.push(v
);}end
[p
]+=end
[fail
[p
]];}}int f
[1005][N
];inline int dp(int n
){memset(f
,-1,sizeof(f
));f
[0][0]=0;for(int i
=0;i
<n
;i
++)for(int j
=0;j
<=tot
;j
++){if(f
[i
][j
]==-1)continue;for(int c
=0;c
<3;c
++)chemx(f
[i
+1][nxt
[j
][c
]],f
[i
][j
]+end
[nxt
[j
][c
]]);}int res
=0;for(int i
=0;i
<=tot
;i
++)chemx(res
,f
[n
][i
]);return res
;}
}
int n
,m
;
char s
[N
];
int main(){n
=read(),m
=read();for(int i
=1;i
<=n
;i
++)scanf("%s",s
+1),Ac
::insert(s
);Ac
::build();cout
<<Ac
::dp(m
);
}
總結
以上是生活随笔為你收集整理的【USACO12JAN】—视频游戏的连击Video Game Combos（AC自动机+dp）的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
