首页 > ACM题库 > HDU-杭电 > HDU 4057-Rescue the Rabbit-动态规划-[解题报告]HOJ
2015
04-16

HDU 4057-Rescue the Rabbit-动态规划-[解题报告]HOJ

Rescue the Rabbit

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

2 4
ATG 4
TGC -3

1 6
TGC 4

4 1
A -1
T -2
G -3
C -4

样例输出:

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.

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by—cxlove

题目:给出一些模式串,每个串有一定的价值,现在构造一个长度为M的串,问最大的价值为多少,每个模式串最多统计一次。

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

11年大连现场赛的题目,不算非常难。

由于每个模式串最多统计一次,也算是降低了难度,最多10个串,容易想至于状态压缩。

Trie树上的状态最多1000个,100*10,而最终的串长度最多为100

容易想到的DP,dp[i][j][k],表示长度为i的串,位于Trie上的状态j,模式串的状态为k的最大价值。

这个复杂度为100*1024*1000,题目给了10s,还是可以搞的,但是空间不够,只能用滚动数组了。

先建立Trie树,以及失败指针,对于每一个结点,标号,静态的方便点。

最终DP,通过模式串的状态确定当前价值

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define eps 1e-10
#define N 100005
#define inf 1<<20
#define zero(a) (fabs(a)<eps)
#define lson (step<<1)
#define rson (step<<1|1)
using namespace std;
struct Trie{
    int next[4],fail;
    int end;
    void Init(){next[0]=next[1]=next[2]=next[3]=0;fail=end=0;}
}tree[N];
int dp[2][1005][1<<10];
char str[105];
int val[105],tot;
int id(char ch){
    if(ch=='A') return 0;
    if(ch=='T') return 1;
    if(ch=='G') return 2;
    return 3;
}
void Insert(char *s,int len,int k){
    int p=0;
    for(int i=0;i<len;i++){
        int q=id(s[i]);
        if(tree[p].next[q]==0){
            tree[++tot].Init();
            tree[p].next[q]=tot;
        }
        p=tree[p].next[q];
    }
    tree[p].end|=(1<<k);
}
void Bulid_Fail(){
    int que[N];
    int head=0,tail=0;
    que[tail++]=0;
    while(head<tail){
        int p=que[head++];
        for(int i=0;i<4;i++){
            if(tree[p].next[i]==0)
                tree[p].next[i]=tree[tree[p].fail].next[i];
            else{
                int q=tree[p].next[i];
                if(p)
                    tree[q].fail=tree[tree[p].fail].next[i];
                tree[q].end|=tree[tree[q].fail].end;
                que[tail++]=q;
            }
        }
    }
}
int n,m;
int get(int state){
    int ans=0;
    for(int i=0;i<n;i++)
        if(state&(1<<i))
           ans+=val[i];
    return ans;
}
void DP(){
    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<=tot;j++){
            for(int k=0;k<4;k++){
                for(int r=0;r<(1<<n);r++){
                    if(dp[(i+1)&1][j][r])
                        dp[i&1][tree[j].next[k]][r|tree[tree[j].next[k]].end]=1;
                }
            }
        }
    }
    int ans=-inf;
    for(int j=0;j<(1<<n);j++)
        for(int i=0;i<=tot;i++)
           if(dp[m&1][i][j]){
              ans=max(ans,get(j));
              break;
           }
    if(ans<0) puts("No Rabbit after 2012!");
    else printf("%d\n",ans);
}
int main(){
    freopen("1.in","r",stdin);
    freopen("2.out","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF){
        tree[0].Init();tot=0;
        for(int i=0;i<n;i++){
            scanf("%s%d",str,&val[i]);
            Insert(str,strlen(str),i);
        }
        Bulid_Fail();
        DP();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7918986


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!