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)


相关推荐

  • 薅羊毛利器—Loon,Cookie放在本地一点也不担心[通俗易懂]

    LoonLoon是一款在iOS系统下的代理工具(目前还没有Android版本),它支持在本地执行js脚本,只需简单配置即可成为薅羊毛利器ps之前的羊毛脚本已经失效了下载可以去美区AppStore下载,价格$4.99,需要有一个美区的AppleId账号,并且充值美元可以去某宝或拼夕夕搜索并购买,价格大概在¥9.99配置然后将下面框里面的配置赋值粘贴进去,点击保存[General]#IPv6支持ipv6=false##skip-proxy和bypass-tun一般不需

  • Android Animation:这一次让你彻底了解 Android Frame Animation「建议收藏」

    Android Animation:这一次让你彻底了解 Android Frame Animation「建议收藏」Android Animation:这一次让你彻底了解 Android Frame Animation

  • Android面试题集锦(2022最新总结)

    Android面试题集锦(2022最新总结)“技术岗年薪总包41W起步,而大厂薪资最高评级SSP总包58W,接近60W,远高于非技术岗人员。”2022年校招,腾讯应届生薪资开奖“第一炮”打响。和去年相比,涨了近10万,且应届生房补也从1250元上升到了4000元。这样的薪资待遇,试问谁不眼馋呢?2021年,行业环境其实稍显颓势,年末那一波大厂裁员更是让互联网人心惶惶。但是,2022年一开端我们会发现,各家依旧抛出高薪的橄榄枝,丝毫未停歇对技术岗人才的抢夺。目前的招聘情况业内人概括为:校招抢人,时间提前,薪资飞涨;同时也不放过任何一个社招.

  • SpringWS创建webservice服务端及客户端

    SpringWS创建webservice服务端及客户端一、服务端下图主要目录结构,这个是完整的,下面,我们就来构建1.1、创建springinitializr,下一步1.2选中springweb,下一步,最后创建1.3导入依赖 <dependencies> <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web- services&

  • offsetWidth和clientWidth

    offsetWidth和clientWidth在項目

  • 解决主页被 hao.360.cn 劫持 及 分析[通俗易懂]

    解决主页被 hao.360.cn 劫持 及 分析[通俗易懂]解决主页被hao.360.cn劫持及分析 解决办法:1.删除注册表HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Mslmedia2.重启3.删除驱动C:\WINDOWS\system32\DRIVERS\Mslmedia.sys搞定现象:打开任何浏览器,主页被hao.360.cn劫持。跳

发表回复

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

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