A rabbit's genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only 'A', 'G', 'T', 'C'. There is no doubt that Dr. X had a in-depth research on the rabbits' genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.
We can make a example, if a rabbit has gene segment "ATG", its W would plus 4; and if has gene segment "TGC", its W plus -3. So if a rabbit's gene string is "ATGC", its W is 1 due to ATGC contains both "ATG"(+4) and "TGC"(-3). And if another rabbit's gene string is "ATGATG", its W is 4 due to one gene segment can be calculate only once.
Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit.
The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit's W.
case 1:we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
const int N=;
int a[],tot;
struct Node
{
Node *fail;
Node *son[];
int flag;
int id;
}node[N],*root;
queue<Node*>Q;
bool dp[][N][]; int f(char c)
{
if(c=='A') return ;
if(c=='G') return ;
if(c=='T') return ;
if(c=='C') return ;
}
void insert(string s,int id)
{
Node *now=root;
for(int i=;i<s.length();i++)
{
int x=f(s[i]);
if(now->son[x]==NULL) now->son[x]=&node[tot++];
now=now->son[x];
}
now->flag|=(<<(id-));
}
void build()
{
Q.push(root);
while(!Q.empty())
{
Node *now=Q.front(); Q.pop();
for(int i=;i<;i++)
{
if(now->son[i])
{
Node *p=now->fail;
while(p&&(!(p->son[i]))) p=p->fail;
now->son[i]->fail=(p)?(p->son[i]):root;
now->son[i]->flag|=now->son[i]->fail->flag;
Q.push(now->son[i]);
}
else now->son[i]=(now!=root)?now->fail->son[i]:root;
}
}
}
void init()
{
tot=;
root=&node[];
memset(dp,,sizeof(dp));
while(!Q.empty()) Q.pop();
for(int i=;i<N;i++)
{
node[i].fail=NULL;
node[i].flag=;
node[i].id=i;
for(int j=;j<;j++) node[i].son[j]=NULL;
}
}
int main()
{
int n,l;
while(scanf("%d%d",&n,&l)!=EOF)
{
init();
for(int i=;i<=n;i++)
{
string s; cin>>s;
insert(s,i);
scanf("%d",&a[i]);
}
build();
dp[][][]=;
int cn=;
for(int i=;i<l;i++)
{
cn^=;
memset(dp[cn],,sizeof(dp[cn]));
for(int j=;j<tot;j++)
{
for(int s=;s<(<<n);s++)
{
if(!dp[cn^][j][s]) continue;
for(int k=;k<;k++)
{
int x=node[j].son[k]->id;
int f=node[j].son[k]->flag;
dp[cn][x][s|f]=;
}
}
}
}
int ans=-;
for(int i=;i<tot;i++)
{
for(int s=;s<(<<n);s++)
{
if(!dp[cn][i][s]) continue;
int tmp=;
int x=s;
for(int k=;k<=n;k++)
{
if(x&) tmp+=a[k];
x>>=;
}
ans=max(ans,tmp);
}
}
if(ans<) puts("No Rabbit after 2012!");
else printf("%d\n",ans);
}
return ;
}
hdu 4057--Rescue the Rabbit(AC自动机+状压DP)的更多相关文章
-
HDU 4057 Rescue the Rabbit ( AC自动机 + 状态压缩DP )
模板来自notonlysuccess. 模式串只有10个,并且重复出现的分值不累加,因此很容易想到状态压缩. 将模式串加入AC自动机,最多有10*100个状态. dp[i][j][k]:串长为i,在T ...
-
zoj3545Rescue the Rabbit (AC自动机+状压dp+滚动数组)
Time Limit: 10 Seconds Memory Limit: 65536 KB Dr. X is a biologist, who likes rabbits very much ...
-
HDU 3247 Resource Archiver(AC自动机 + 状压DP + bfs预处理)题解
题意:目标串n( <= 10)个,病毒串m( < 1000)个,问包含所有目标串无病毒串的最小长度 思路:貌似是个简单的状压DP + AC自动机,但是发现dp[1 << n][ ...
-
hdu 6086 -- Rikka with String(AC自动机 + 状压DP)
题目链接 Problem Description As we know, Rikka is poor at math. Yuta is worrying about this situation, s ...
-
HDU 2825 Wireless Password(AC自动机 + 状压DP)题解
题意:m个密码串,问你长度为n的至少含有k个不同密码串的密码有几个 思路:状压一下,在build的时候处理fail的时候要用 | 把所有的后缀都加上. 代码: #include<cmath> ...
-
HDU 4057 Rescue the Rabbit(AC自动机+DP)
题目链接 一个数组开小了一点点,一直提示wa,郁闷,这题比上个题简单一点. #include <iostream> #include <cstring> #include &l ...
-
HDU - 2825 Wireless Password (AC自动机+状压DP)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=2825 题意:给一些字符串,构造出长度为n的字符串,它至少包含k个所给字符串,求能构造出的个数. 题解: ...
-
hdu 2825 aC自动机+状压dp
Wireless Password Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others ...
-
BZOJ1559 [JSOI2009]密码 【AC自动机 + 状压dp】
题目链接 BZOJ1559 题解 考虑到这是一个包含子串的问题,而且子串非常少,我们考虑\(AC\)自动机上的状压\(dp\) 设\(f[i][j][s]\)表示长度为\(i\)的串,匹配到了\(AC ...
随机推荐
-
lua解释执行脚本流程
#include "lua.hpp" #include <iostream> using namespace std; #pragma comment(lib, &qu ...
-
40 个让你的网站更加友好的 jQuery 插件
一个插件的基本功能是执行一个含有元素集合的函数数组.每个方法和jQuery核心组成一个插件,如.fadeOut()或.addClass().一个jQuery插件是一个基本的可以扩充jQuery 原型对 ...
-
sqlserver表分区
参考:http://www.cnblogs.com/knowledgesea/p/3696912.html 及百度搜索sqlserver表分区 create partition function sg ...
-
GPU 的硬件基本概念,Cuda和Opencl名词关系对应
GPU 的硬件基本概念 Nvidia的版本: 实际上在 nVidia 的 GPU 里,最基本的处理单元是所谓的 SP(Streaming Processor),而一颗 nVidia 的 GPU 里,会 ...
-
pinpoint初始化hbase脚本报错
今天在部署pinpoint的时候,执行创建表语句的脚本,报表已经存在的错误,但是那个hbase数据目录是刚创建的,表肯定是不存在的 <property> <name>hbase ...
-
ChemDraw 16最新版本发布 更效率科研的首选
ChemDraw一直是全球领先的科学绘图软件,致力于为科学家.教师以及学生提供最新的智能应用程序.ChemDraw 16版本相较于15版本做出了较大的改进,大大缩短科研时间,提高科研效率.扩展Name ...
-
Denoise Autoencoder简单理解
自编码器通过学习隐含特征来表达原始数据,那什么是denoise autoencoder呢? 关于Autoencoder参考:http://blog.csdn.net/on2way/article/de ...
-
csu 1552(米勒拉宾素数测试+二分图匹配)
1552: Friends Time Limit: 3 Sec Memory Limit: 256 MBSubmit: 723 Solved: 198[Submit][Status][Web Bo ...
-
log4j中将SocketAppender将日志内容发送到远程服务器
1.服务端配置 1)服务端配置文件log4j-server.properties #Define a narrow log category. A category like debug will p ...
-
Vue nodejs商城项目-商品的分页、排序、筛选
.分页 ,要查第3页的数据,则跳过2*8条数据,然后返回8条数据. 在实现滚动加载时,页面刚一加载完成并不需要请求所有数据,当用户下拉到页面底部时,再去请求数据并拼接到商品数据列表中. 通过vue-i ...