hdu 4057 AC自己主动机+状态压缩dp

hdu 4057 AC自己主动机+状态压缩dp

大家好,又见面了,我是全栈君。

http://acm.hdu.edu.cn/showproblem.php?pid=4057

Problem Description
Dr. X is a biologist, who likes rabbits very much and can do everything for them. 2012 is coming, and Dr. X wants to take some rabbits to Noah’s Ark, or there are no rabbits any more.

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.

 


Input
There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10),l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits’ genes.

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.

 


Output
For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output “No Rabbit after 2012!”.

 


Sample Input
   
   
2 4 ATG 4 TGC -3 1 6 TGC 4 4 1 A -1 T -2 G -3 C -4

 


Sample Output
   
   
4 4 No Rabbit after 2012!
Hint
case 1:we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc. case 2:we can find a rabbit whose gene string is TGCTGC(4), or TGCCCC(4) etc. case 3:any gene string whose length is 1 has a negative W.

/**
hdu 4057 AC自己主动机+状态压缩dp
题目大意:给定一些字符串(ATGC组成)。相同用该四个字符组成一个长度为l的字符串,若该字符串包括给定串的一个作为子串,那么就要
          加上这个给定串的值,问最后该字符串的最大值为多少
解题思路:建立自己主动机,然后在上面跑,假设不要求每一个串的权值仅仅能获取一次,那么直接跑来跑去的即可,可是由于仅仅能取一次,串非常少,
          能够状态压缩DP,dp[i][j][k]记录前i个字符走到j状态而且已经获得的串状态为k时的最优解。滚动数组优化空间
*/
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int inf=1e9+7;
const int maxn=1005;
int dp[2][maxn][1<<10];
int n,m,val[15];
struct Trie
{
    int next[maxn][4],fail[maxn],_end[maxn];
    int root,L;
    int change(char ch)
    {
        if(ch=='A')return 0;
        else if(ch=='T')return 1;
        else if(ch=='G')return 2;
        return 3;
    }
    int newnode()
    {
        for(int i=0; i<4; i++)
        {
            next[L][i]=-1;
        }
        _end[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void Insert(char *buf,int id)
    {
        int len=strlen(buf);
        int now=root;
        for(int i=0; i<len; i++)
        {
            int q=change(buf[i]);
            if(next[now][q]==-1)
                next[now][q]=newnode();
            now=next[now][q];
        }
        _end[now]|=(1<<id);
    }
    void build()
    {
        queue<int>Q;
        fail[root]=root;
        for(int i=0; i<4; i++)
        {
            if(next[root][i]==-1)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        }
        while(!Q.empty())
        {
            int now=Q.front();
            Q.pop();
            _end[now]|=_end[fail[now]];
            for(int i=0; i<4; i++)
            {
                if(next[now][i]==-1)
                {
                    next[now][i]=next[fail[now]][i];
                }
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }
    int get(int s)
    {
        int ans=0;
        for(int i=0; i<n; i++)
        {
            if(s&(1<<i))
                ans+=val[i];
        }
        return ans;
    }
    void solve()
    {
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        for(int i=1; i<=m; i++)
        {
            memset(dp[i&1],0,sizeof(dp[i&1]));
            for(int j=0; j<L; j++)
            {
                for(int k=0; k<4; k++)
                {
                    int x=next[j][k];
                    for(int r=0; r<(1<<n); r++)
                    {
                        if(dp[(i+1)&1][j][r])
                        {
                            dp[i&1][x][r|_end[x]]=1;
                        }
                    }
                }
            }
        }
        int ans=-inf;
        for(int j=0; j<(1<<n); j++)
        {
            for(int i=0; i<L; i++)
            {
                if(dp[m&1][i][j])
                {
                    ans=max(ans,get(j));
                }
            }
        }
        if(ans<0)puts("No Rabbit after 2012!");
        else printf("%d\n",ans);
    }
} t;
char s[1005];
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        t.init();
        for(int i=0; i<n; i++)
        {
            int x;
            scanf("%s%d",s,&val[i]);
            t.Insert(s,i);
        }
        t.build();
        t.solve();
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116254.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • vue前端ui框架_详细讲解帕米尔的春天

    vue前端ui框架_详细讲解帕米尔的春天本文章描述的是Swagger3.0的内容,与Swagger2.0内容有较大差别。接口描述在3.0中通过Swagger规范(一个JSON文件)来描述,Swagger2.0是通过在接口中提供一系列注解来描述的。 1.集成Swagger    Swagger提供了一组静态页面,可以在SpringBoot应用中集成这些静态页面,直接访问静态页面,并打开指定的Swagger规范,就可以…

    2022年10月30日
  • Python正则表达式语法_re正则表达式语法

    Python正则表达式语法_re正则表达式语法python正则表达式的语法及使用概念:按照程序员的指示,字符串里提取你要的数据。应用:爬虫清洗数据,匹配电话,匹配邮箱,匹配账号……最重要的就是(.*?)正则语法(元字符)1、?:前面的内容出现0-1次2、+:前面的内容出现1-多次3、*:前面的内容出现0-多次‘’’正则(Regular):记住的点:1、(.?)2、re.findall()结果是一个列表3、用(.?)的是后,一定要复制,而不是手敲!‘’’importre‘’’正则语法(普通字符):

  • java WebSocket客户端断线重连 | 实用代码框架「建议收藏」

    java WebSocket客户端断线重连 | 实用代码框架「建议收藏」在工作中是否会遇到实用websocket客户端连接服务端的时候,网络波动,服务端断连的情况。会导致客户端被动断开连接。为了解决这个问题,需要对被动断开连接的情况进行捕获,并重新创建连接。这篇文章主要是提供可以直接使用的断线重连websocket客户端代码。

  • #转载 基于C#通过OPC UA/DA访问PLC学习网站

    #转载 基于C#通过OPC UA/DA访问PLC学习网站#转载#基于C#通过OPCUA/DA访问PLC学习网站今年刚入职的新手,第一次接触OPCUA、OPCDA、C#、PLC,全靠各种百度,经过一个多星期的摸索,基本算是刚入门吧,下面把学习过程中收藏的一些实用的文章和大家分享一下,绝对可以让你少走很多弯路。1.C#读写opcua服务器,浏览所有节点,读写节点,读历史数据,调用方法,订阅,批量订阅操作-dathlin2.C#OPCUA服务器OPCUA网关三菱西门子欧姆龙Modbus转OPCUA服务器可配置的OPCUA服务器网

    2022年10月18日
  • 发卡网源码(企业和个人发卡网源码二合一)及代理系统附搭建教程

    发卡网源码(企业和个人发卡网源码二合一)及代理系统附搭建教程  最近,有网友问到,自己在上传发卡网源码的时候,总是各种出错。比如404、或者数据库错误等等。  如果通过自己上传源码,安装的时候还是出现各种错误。  附源码及演示:fakaysw.top  那么,我建议可以使用企业级发卡网源码的一键部署功能。  这个功能对于新手来说,非常好用,十分省心。  第一种方式是,找到宝塔面板的“软件商店”-“发卡网源码一键部署”  看一下列表中有没有你想要安装的程序,如果没有找到,看下面的第二种方式  第二种方式,找到“软件商店”,在搜索框搜索“发卡网一键

  • ie浏览器activexobject_ie8 object.defineproperty

    ie浏览器activexobject_ie8 object.defineproperty切记:ActiveX是微软的东西,故而这玩意儿只有IE才支持!JavaScript中ActiveXObject对象是启用并返回Automation对象的引用,javaScript中利用ActiveXObject来创建FileSystemObject操作文件。一、功能实现核心:FileSystemObject对象要在javascript中实现文件操作功能,主要就是依

    2022年10月11日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号