当前位置：网站首页>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.
边栏推荐
- STM32WB55的FUS更新及协议栈固件烧写方法
- 如何在WPF中设置Grid ColumnDefinitions的样式
- DSPE-PEG-PDP,DSPE-PEG-OPSS,磷脂-聚乙二醇-巯基吡啶可减少肽的免疫原性
- pat链表专题训练+搜索专题
- laravel报错：TokenMismatchException in VerifyCsrfToken.php line 68:
- Cholesterol-PEG-Thiol,CLS-PEG-SH,胆固醇-聚乙二醇-巯基用于改善溶解度
- 企业数据打通有什么好处？不同行业怎么解决数据打通难题？
- 小满nestjs（第六章 nestjs cli 常用命令）
- 基于Web的疫情隔离区订餐系统
- 华为云创新中心助力启泰智能 补齐中小模具企业数字化能力短板
猜你喜欢
Can I make a TCP connection without accept?
Ankerui supports Ethernet communication, profibus communication embedded energy meter APM guiding technical requirements-Susie Week
Toronto Research Chemicals加米霉素-d4说明书
小满nestjs（第四章 前置知识装饰器-实现一个GET请求）
Win11找不到Internet Explore怎么办
【kali-权限提升】（4.2.6）社会工程学工具包（中）：中间人攻击工具Ettercap
【Jmeter】分布式搭建
DSPE-PEG-Azide，DSPE-PEG-N3，磷脂-聚乙二醇-叠氮可和DBCO直接反应
IS31FL3737B general 12 x 12 LED drive 40 QFN I2C 42 ma
使用Mock技术模拟数据
随机推荐
企业数据打通有什么好处？不同行业怎么解决数据打通难题？
时序攻击
如何在WPF中设置Grid ColumnDefinitions的样式
【IoT毕设】STM32与机智云自助开发平台的宠物智能喂养系统
渗透测试-对新型内存马webshell的研究
明明加了唯一索引，为什么还是产生重复数据？
小满nestjs（第五章 nestjs cli）
Access control knowledge
使用Mock技术模拟数据
DSPE-PEG-PDP,DSPE-PEG-OPSS,磷脂-聚乙二醇-巯基吡啶可减少肽的免疫原性
Transformer如何用于3D视觉？阿联酋MBZUAI最新《3D视觉Transformers处理》综述，涵盖100+种方法
matlab neural network ANN classification
安科瑞支持以太网通讯、profibus通讯嵌入式电能表APM指导性技术要求-Susie 周
基于网络数据流的未知密码协议逆向分析
一图详解沃土云创计划高校教师参与全流程
[Free column] APK dynamic reverse application of Android security [Three Smali injection methods]
韩国网络安全体系特征与发展前景
字节二面问的MySQL，差点没答好
请问一下flink cdc mysql source 报这种错怎么处理呢？我都设置了useSSL=f
[Free column] Xposed plug-in development for Android security [from scratch] tutorial