当前位置：网站首页>hdu 3341 Lost's revenge(dp+Ac自动机)
hdu 3341 Lost's revenge(dp+Ac自动机)
2022-08-09 19:20:00 【51CTO】
题目： http://acm.hdu.edu.cn/showproblem.php?pid=3341
Lost's revenge
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3369 Accepted Submission(s): 896
Problem Description
Lost and AekdyCoin are friends. They always play "number game"(A boring game based on number theory) together. We all know that AekdyCoin is the man called "nuclear weapon of FZU,descendant of Jingrun", because of his talent in the field of number theory. So Lost had never won the game. He was so ashamed and angry, but he didn't know how to improve his level of number theory.
One noon, when Lost was lying on the bed, the Spring Brother poster on the wall(Lost is a believer of Spring Brother) said hello to him! Spring Brother said, "I'm Spring Brother, and I saw AekdyCoin shames you again and again. I can't bear my believers were being bullied. Now, I give you a chance to rearrange your gene sequences to defeat AekdyCoin!".
It's soooo crazy and unbelievable to rearrange the gene sequences, but Lost has no choice. He knows some genes called "number theory gene" will affect one "level of number theory". And two of the same kind of gene in different position in the gene sequences will affect two "level of number theory", even though they overlap each other. There is nothing but revenge in his mind. So he needs you help to calculate the most "level of number theory" after rearrangement.
Input
There are less than 30 testcases.
For each testcase, first line is number of "number theory gene" N(1<=N<=50). N=0 denotes the end of the input file.
Next N lines means the "number theory gene", and the length of every "number theory gene" is no more than 10.
The last line is Lost's gene sequences, its length is also less or equal 40.
All genes and gene sequences are only contains capital letter ACGT.
Output
For each testcase, output the case number(start with 1) and the most "level of number theory" with format like the sample output.
Sample Input
3
AC
CG
GT
CG
AT
1
AA
AAA
0
Sample Output
Case 1: 3 Case 2: 2
做这题真的是闹心，只怪自己开始没有估计好时间复杂度瞎折腾，走了不少弯路。第一次想用Ac自动机检验长串的各种排列取最大值即可，但是长串有可能存在字符想通过的情况，排列一定小于length！，怎样才能把所有的非重复的字符串排列找出来呢？《C语言名题精选百则》里有个旋转法，但是我研究了半天也没有把重复的去掉。后来发现next_permutation是个好东西，可以除去重复的串，但前提是初始串是单调的，这简单，我用一个sort不就可以了吗？开心啊。。
TLE：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using
namespace
std;
int
ans;
char
word[
15],
mystring[
50];
struct
node{
int
count;
node
*
next[
4],
*
fail;
node(){
count
=
0;
fail
=
NULL;
memset(
next,
0,
sizeof(
next));
}
};
node
*
root;
int
getdex(
char
a){
int
ans;
if(
a
==
'A')
ans
=
0;
else
if(
a
==
'C')
ans
=
1;
else
if(
a
==
'G')
ans
=
2;
else
ans
=
3;
return
ans;
}
void
insert(
char
*
s){
int
length
=
strlen(
s);
node
*
p
=
root;
for(
int
i
=
0;
i
<
length;
i
++){
int
dex
=
getdex(
s[
i]);
if(
p
->
next[
dex]
==
0)
p
->
next[
dex]
=
new
node();
p
=
p
->
next[
dex];
}
p
->
count
++;
}
node
*
que[
1000];
void
build_ac(){
int
head,
tail;
head
=
tail
=
0;
que[
tail
++]
=
root;
while(
head
<
tail){
node
*
p
=
que[
head
++],
*
temp
=
NULL;
for(
int
i
=
0;
i
<
4;
i
++){
if(
p
->
next[
i]){
if(
p
==
root)
p
->
next[
i]
->
fail
=
root;
else {
temp
=
p
->
fail;
while(
temp){
if(
temp
->
next[
i]){
p
->
next[
i]
->
fail
=
temp
->
next[
i];
break;
}
temp
=
temp
->
fail;
}
if(
!
temp)
p
->
next[
i]
->
fail
=
root;
}
que[
tail
++]
=
p
->
next[
i];
}
}
}
}
void
del(
node
*
p){
if(
p
==
NULL)
return ;
for(
int
i
=
0;
i
<
4;
i
++)
del(
p
->
next[
i]);
delete
p;
}
int
query(
int
str[],
int
str_len){
int
i,
dex,
result
=
0;
node
*
p
=
root;
for(
i
=
0;
i
<
str_len;
i
++){
while(
p
->
next[
str[
i]]
==
NULL
&&
p
!=
root)
p
=
p
->
fail;
p
=
p
->
next[
str[
i]];
if(
!
p)
p
=
root;
node
*
temp
=
p;
while(
temp
!=
root){
//&&temp->count!=-1
result
+=
temp
->
count;
//temp->count=-1;
temp
=
temp
->
fail;
}
}
return
result;
}
void
show(
int
str[],
int
len){
for(
int
i
=
0;
i
<
len;
i
++)
cout
<<
str[
i]
<<
" ";
cout
<<
endl;
}
int
main()
{
//freopen("cin.txt","r",stdin);
int
n,
ca
=
1;
while(
cin
>>
n
&&
n){
root
=
new
node();
while(
n
--){
scanf(
"%s",
word);
insert(
word);
}
build_ac();
scanf(
"%s",
mystring);
int
str_len
=
strlen(
mystring);
int
str[
50];
for(
int
i
=
0;
i
<
str_len;
i
++){
str[
i]
=
getdex(
mystring[
i]);
}
int
ans
=
0;
sort(
str,
str
+
str_len);
do{
ans
=
max(
ans,
query(
str,
str_len));
}
while(
next_permutation(
str,
str
+
str_len));
printf(
"Case %d: %d\n",
ca
++,
ans);
del(
root);
}
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
- 108.
- 109.
- 110.
- 111.
- 112.
郁闷啊，TLE了，是不是指针太耗时间了，于是我又把指针改成数组：
TLE：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using
namespace
std;
int
ans,
top;
char
word[
15],
mystring[
50];
struct
node{
int
next[
4],
fail;
int
count;
node(){
count
=
0;
fail
=
NULL;
memset(
next,
0,
sizeof(
next));
}
}
tree[
510];
int
getdex(
char
a){
int
ans;
if(
a
==
'A')
ans
=
0;
else
if(
a
==
'C')
ans
=
1;
else
if(
a
==
'G')
ans
=
2;
else
ans
=
3;
return
ans;
}
void
insert(
char
*
s){
int
length
=
strlen(
s),
p
=
0;
for(
int
i
=
0;
i
<
length;
i
++){
int
dex
=
getdex(
s[
i]);
if(
tree[
p].
next[
dex]
==
0){
top
++;
tree[
p].
next[
dex]
=
top;
}
p
=
tree[
p].
next[
dex];
}
tree[
p].
count
++;
}
void
build_ac(){
queue
<
int
>
q;
q.
push(
0);
int
i,
p,
cur,
son;
while(
!
q.
empty()){
p
=
q.
front();
q.
pop();
for(
int
i
=
0;
i
<
4;
i
++){
if(
tree[
p].
next[
i]){
son
=
tree[
p].
next[
i];
if(
p
==
0)
tree[
son].
fail
=
p;
else {
cur
=
tree[
p].
fail;
while(
cur
&&
tree[
cur].
next[
i]
==
0)
cur
=
tree[
cur].
fail;
tree[
son].
fail
=
tree[
cur].
next[
i];
}
if(
tree[
tree[
son].
fail].
count)
tree[
son].
count
+=
tree[
tree[
son].
fail].
count;
q.
push(
son);
}
else
tree[
p].
next[
i]
=
tree[
tree[
p].
fail].
next[
i];
}
}
}
int
query(
int
str[],
int
str_len){
int
i,
dex,
result
=
0;
int
p
=
0;
for(
i
=
0;
i
<
str_len;
i
++){
while(
tree[
p].
next[
str[
i]]
==
NULL
&&
p
!=
0)
p
=
tree[
p].
fail;
p
=
tree[
p].
next[
str[
i]];
//p=p->next[str[i]];
if(
!
p)
p
=
0;
int
temp
=
p;
while(
temp
!=
0){
//&&temp->count!=-1
result
+=
tree[
temp].
count;
//temp->count=-1;
temp
=
tree[
temp].
fail;
}
}
return
result;
}
void
show(
int
str[],
int
len){
for(
int
i
=
0;
i
<
len;
i
++)
cout
<<
str[
i]
<<
" ";
cout
<<
endl;
}
int
main()
{
//freopen("cin.txt","r",stdin);
int
n,
ca
=
1;
while(
cin
>>
n
&&
n){
//tree[0].node();
while(
n
--){
scanf(
"%s",
word);
insert(
word);
}
build_ac();
scanf(
"%s",
mystring);
int
str_len
=
strlen(
mystring);
int
str[
50];
for(
int
i
=
0;
i
<
str_len;
i
++){
str[
i]
=
getdex(
mystring[
i]);
}
int
ans
=
0;
sort(
str,
str
+
str_len);
do{
ans
=
max(
ans,
query(
str,
str_len));
}
while(
next_permutation(
str,
str
+
str_len));
printf(
"Case %d: %d\n",
ca
++,
ans);
memset(
tree,
0,
sizeof(
tree));
}
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
还是TLE！能不能愉快的玩耍了？仔细分析：原来40长度4种最小单位的长串排列估算有：40!/10!/10!/10!/10!=4.71e21，哎，一开始怎么不想想这个问题，还做了半天无用功！接下来怎么办呢？看了大神们的思路，DP啊，空间换时间。组合情况：11*11*11*11<15000。真是巧妙啊。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using
namespace
std;
int
ans,
top;
char
word[
15],
mystring[
50];
struct
node{
int
next[
4],
fail;
int
count;
}
tree[
510];
int
getdex(
char
a){
int
ans;
if(
a
==
'A')
ans
=
0;
else
if(
a
==
'C')
ans
=
1;
else
if(
a
==
'G')
ans
=
2;
else
ans
=
3;
return
ans;
}
void
insert(
char
*
s){
int
length
=
strlen(
s),
p
=
0;
for(
int
i
=
0;
i
<
length;
i
++){
int
dex
=
getdex(
s[
i]);
if(
tree[
p].
next[
dex]
==
0){
top
++;
tree[
p].
next[
dex]
=
top;
}
p
=
tree[
p].
next[
dex];
}
tree[
p].
count
++;
}
void
build_ac(){
queue
<
int
>
q;
q.
push(
0);
int
i,
p,
cur,
son;
while(
!
q.
empty()){
p
=
q.
front();
q.
pop();
for(
int
i
=
0;
i
<
4;
i
++){
if(
tree[
p].
next[
i]){
son
=
tree[
p].
next[
i];
if(
p
==
0)
tree[
son].
fail
=
p;
else {
cur
=
tree[
p].
fail;
while(
cur
&&
tree[
cur].
next[
i]
==
0)
cur
=
tree[
cur].
fail;
tree[
son].
fail
=
tree[
cur].
next[
i];
}
if(
tree[
tree[
son].
fail].
count)
tree[
son].
count
+=
tree[
tree[
son].
fail].
count;
q.
push(
son);
}
else
tree[
p].
next[
i]
=
tree[
tree[
p].
fail].
next[
i];
}
}
}
int
myhash[
41][
41][
41][
41];
int
ta,
tc,
tg,
tt;
int
dp[
15000][
505];
void
mydp(
char
*
S)
{
ta
=
tc
=
tg
=
tt
=
0;
int
i,
j,
k,
l,
num
=
0;
for(
i
=
0;
S[
i]
!=
0;
i
++)
if(
S[
i]
==
'A')
ta
++;
else
if(
S[
i]
==
'C')
tc
++;
else
if(
S[
i]
==
'G')
tg
++;
else
tt
++;
for(
i
=
0;
i
<=
ta;
i
++)
for(
j
=
0;
j
<=
tc;
j
++)
for(
k
=
0;
k
<=
tg;
k
++)
for(
l
=
0;
l
<=
tt;
l
++)
myhash[
i][
j][
k][
l]
=
num
++;
}
void
solve(
int
ca)
{
int
i,
j,
k,
l,
p,
q,
son,
x1,
x2,
mmax
=
0;
dp[
0][
0]
=
0;
for(
i
=
0;
i
<=
ta;
i
++)
for(
j
=
0;
j
<=
tc;
j
++)
for(
k
=
0;
k
<=
tg;
k
++)
for(
l
=
0;
l
<=
tt;
l
++)
{
if(
i
+
j
+
k
+
l
==
0)
continue;
x1
=
myhash[
i][
j][
k][
l];
for(
p
=
0;
p
<=
top;
p
++)
{
for(
q
=
0;
q
<
4;
q
++)
{
if(
q
==
0
&&
i
-
1
>=
0)
x2
=
myhash[
i
-
1][
j][
k][
l];
else
if(
q
==
1
&&
j
-
1
>=
0)
x2
=
myhash[
i][
j
-
1][
k][
l];
else
if(
q
==
2
&&
k
-
1
>=
0)
x2
=
myhash[
i][
j][
k
-
1][
l];
else
if(
q
==
3
&&
l
-
1
>=
0)
x2
=
myhash[
i][
j][
k][
l
-
1];
else
continue;
if(
dp[
x2][
p]
==-
1)
continue;
son
=
tree[
p].
next[
q];
dp[
x1][
son]
=
max(
dp[
x1][
son],
dp[
x2][
p]
+
tree[
son].
count);
if(
dp[
x1][
son]
>
mmax)
mmax
=
dp[
x1][
son];
}
}
}
printf(
"Case %d: ",
ca);
printf(
"%d\n",
mmax);
}
int
main()
{
//freopen("cin.txt","r",stdin);
int
n,
ca
=
1;
while(
cin
>>
n
&&
n){
top
=
0;
memset(
dp,
-
1,
sizeof(
dp));
while(
n
--){
scanf(
"%s",
word);
insert(
word);
}
build_ac();
scanf(
"%s",
mystring);
mydp(
mystring);
solve(
ca
++);
memset(
tree,
0,
sizeof(
tree));
}
return
0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
- 108.
- 109.
- 110.
- 111.
- 112.
- 113.
- 114.
- 115.
- 116.
- 117.
- 118.
- 119.
- 120.
- 121.
- 122.
- 123.
- 124.
- 125.
- 126.
- 127.
- 128.
- 129.
- 130.
- 131.
- 132.
- 133.
- 134.
- 135.
build_ac()内和普通的失败指针建立函数相比最重要的两句（//后面的两句）：
直接在建立失败指针时就更新各个节点的count。后面的状态转移过程直接使用。
普通的build_ac():
void
build_ac(){
queue
<
int
>
q;
q.
push(
0);
int
i,
p,
cur,
son;
while(
!
q.
empty()){
p
=
q.
front();
q.
pop();
for(
int
i
=
0;
i
<
4;
i
++){
if(
tree[
p].
next[
i]){
son
=
tree[
p].
next[
i];
if(
p
==
0)
tree[
son].
fail
=
p;
else {
cur
=
tree[
p].
fail;
while(
cur
&&
tree[
cur].
next[
i]
==
0)
cur
=
tree[
cur].
fail;
tree[
son].
fail
=
tree[
cur].
next[
i];
}
if(
tree[
cur])
tree[
son].
fail
=
0;
q.
push(
son);
}
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
边栏推荐
- Can I make a TCP connection without accept?
- 安科瑞支持以太网通讯、profibus通讯嵌入式电能表APM指导性技术要求-Susie 周
- 访问控制知识
- 【随笔】致19期的小伙伴们
- leetcode二叉搜索树与双向链表
- MySQL笔记-06 基础SQL操作
- Laravel DB批量更新的方法
- Overview of Security Analysis Technology for Smart Home Devices
- 数据分散情况的统计图-盒须图
- MySQL, which is asked on both sides of the byte, almost didn't answer well
猜你喜欢
STM32WB55的FUS更新及协议栈固件烧写方法
leetcode二叉搜索树与双向链表
DSPE-PEG-Silane,DSPE-PEG-SIL,磷脂-聚乙二醇-硅烷修饰二氧化硅颗粒用
![[Free column] APK dynamic reverse application of Android security [Three Smali injection methods]](/img/11/39a25d86c9486bb5201659bbbeaa36.png)
[Free column] APK dynamic reverse application of Android security [Three Smali injection methods]
39. 组合总和 ＆＆ 40. 组合总和2 ＆＆ 216. 组合总和3
【kali-权限提升】（4.2.6）社会工程学工具包（中）：中间人攻击工具Ettercap
【kali-密码攻击】（5.1.1）密码在线破解：Hydra（图形界面）
源码编译安装与yum和rpm软件安装详解
![[Free column] Xposed plug-in development for Android security [from scratch] tutorial](/img/7b/a036ac664c7e27ed7d87e7ee18c05d.png)
[Free column] Xposed plug-in development for Android security [from scratch] tutorial
企业数据打通有什么好处？不同行业怎么解决数据打通难题？
随机推荐
Prometheus Operator 自定义监控添加redis explorer
DP-Differential Privacy概念介绍
没有 accept，我可以建立 TCP 连接吗？
MYSQL记录、自用
poj 1182 食物链（带权并查集）
MySQL, which is asked on both sides of the byte, almost didn't answer well
一千以内的水仙花数
[Free column] Xposed plug-in development for Android security [from scratch] tutorial
tki-tree 树组件控制默认展开第几层数据
请问一下flink cdc mysql source 报这种错怎么处理呢？我都设置了useSSL=f
面试官：Redis 大 key 要如何处理？
获取一段程序运行的时间
痛击面试官 CURD系统也能做出技术含量
MySQL Notes-06 Basic SQL Operations
【IoT毕设】STM32与机智云自助开发平台的宠物智能喂养系统
Definition and Basic Operations of Linear Tables
基于Web的疫情隔离区订餐系统
hdu 2094 产生冠军(STL map || 拓扑 || STL set)
leetcode二叉搜索树与双向链表
顺序表的定义和基本操作