当前位置：网站首页>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.
边栏推荐
- 【图文并茂】如何进行Win7系统的重装
- 顺序表的定义和基本操作
- laravel之phpunit单元测试
- How to deal with keys when Redis is large?
- 如何在WPF中设置Grid ColumnDefinitions的样式
- Queue topic: Implementing stacks with queues
- Characteristics and Development Prospects of Korea's Cyber Security System
- Reverse Analysis of Unknown Cryptographic Protocol Based on Network Data Flow
- mysql duplicate data group multiple latest records
- hdu 1285 确定比赛名次(拓扑排序)
猜你喜欢
39. 组合总和 ＆＆ 40. 组合总和2 ＆＆ 216. 组合总和3
【kali-密码攻击】（5.1.1）密码在线破解：Hydra（图形界面）
MySQL, which is asked on both sides of the byte, almost didn't answer well
阿里二面：没有 accept，能建立 TCP 连接吗？
痛击面试官 CURD系统也能做出技术含量
hdu 2094 产生冠军(STL map || 拓扑 || STL set)
Transformer如何用于3D视觉？阿联酋MBZUAI最新《3D视觉Transformers处理》综述，涵盖100+种方法
Openharmony Lightweight System Experiment--GPIO Lighting
mysql duplicate data group multiple latest records
matlab 神经网络 ANN 分类
随机推荐
NetCore路由的Endpoint模式
MySQL, which is asked on both sides of the byte, almost didn't answer well
php删除字符串的空格
加工制造业智慧采购系统解决方案：助力企业实现全流程采购一体化协同
SqlServer 2016 备份和还原
字节二面问的MySQL，差点没答好
hdu 2647 Reward（拓扑排序)
Cholesterol-PEG-Thiol, CLS-PEG-SH, Cholesterol-PEG-Sulfhydryl for improved solubility
【NOI模拟赛】防AK题（生成函数，单位根，Pollard-Rho）
DSPE-PEG-Silane,DSPE-PEG-SIL,磷脂-聚乙二醇-硅烷修饰二氧化硅颗粒用
新起之秀 DPU，正在掀起数据中心变革！
基于光通信的6G水下信道建模综述
competed中访问ref为undefined
Toronto Research Chemicals盐酸乙环胺应用说明
力扣383-赎金信——哈希映射数组法
poj 1182 食物链（带权并查集）
shell之变量详解，让你秒懂！
[Deep learning] pix2pix GAN theory and code implementation
Cholesterol-PEG-Thiol,CLS-PEG-SH,胆固醇-聚乙二醇-巯基用于改善溶解度
URL Protocol web page to open the application