首页 > ACM题库 > HDU-杭电 > HDU 3341-Lost’s revenge-动态规划-[解题报告]HOJ
2014
03-16

HDU 3341-Lost’s revenge-动态规划-[解题报告]HOJ

Lost’s revenge

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

3
AC
CG
GT
CGAT
1
AA
AAA
0

样例输出:

Case 1: 3
Case 2: 2

       这题没意思,卡时间卡的太紧了,主要就是知道这种类型的状态压缩怎么写就好了。

       假设ACGT的总数分别为num[0],num[1],num[2],num[3],那么对于ACGT的数量分别为ABCD的状态可以记录为:
                     A*(num[1]+1)*(num[2]+1)*(num[3]+1) + B*(num[2]+1)*(num[3]+1)+ C*(num[3]+1) +D。

      

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define N 505
#define Max 4
using namespace std;
int num[N],next[N][4],fail[N];
int cnt,root;
int newnode()
{
    fail[cnt] = 0;
    num[cnt] = 0;
    return cnt++;
}
int hash(char s)
{
    if(s == 'A')return 0;
    if(s == 'C')return 1;
    if(s == 'G')return 2;
    if(s == 'T')return 3;
}
void insert(char *str)
{
    int i=0,s;
    int t = root;
    while(str[i])
    {
        s = hash(str[i]);
        if(next[t][s]==0)
            next[t][s]=newnode();
        t = next[t][s];
        i++;
    }
    num[t]++;
}
void build_ac_automation()
{
    queue<int>q;
    int tmp = root;
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.front();
        q.pop();
        for(int i=0; i<Max; i++)
            if(next[tmp][i]==NULL)
            {
                if(tmp==root)next[tmp][i] = root;
                else next[tmp][i] = next[fail[tmp]][i];
            }
            else
            {
                if(tmp==root)fail[next[tmp][i]] = root;
                else
                {
                    fail[next[tmp][i]] = next[fail[tmp]][i];
                    num[next[tmp][i]]+=num[next[fail[tmp]][i]];
                }
                q.push(next[tmp][i]);
            }
    }
}
char s[50];
int dp[505][11*11*11*11+5];
int sum[4],bit[4];
int main()
{
    int n,i,j,cas = 1;
    while(scanf("%d",&n)&&n)
    {
        cnt = 0;
        root = newnode();
        memset(sum,0,sizeof(sum));
        memset(dp,-1,sizeof(dp));
        memset(next,0,sizeof(next));
        for(i = 1;i<=n;i++)
        {
            scanf("%s",s);
            insert(s);
        }
        build_ac_automation();
        scanf("%s",s);
        int l = strlen(s);
        for(i = 0;i<l;i++)
            sum[hash(s[i])]++;
        bit[0] = (sum[1]+1)*(sum[2]+1)*(sum[3]+1);
        bit[1] = (sum[2]+1)*(sum[3]+1);
        bit[2] = (sum[3]+1);
        bit[3] = 1;
        memset(dp,-1,sizeof(dp));
        dp[root][0] = 0;
        for(int A = 0;A <= sum[0];A++)
            for(int B = 0;B <= sum[1];B++)
                for(int C = 0;C <= sum[2];C++)
                    for(int D = 0;D <= sum[3];D++)
                    {
                        int st = A*bit[0] + B*bit[1] + C*bit[2] + D*bit[3];
                        for(int i = 0;i < cnt;i++)
                            if(dp[i][st] >= 0)
                            {
                                for(int k = 0;k < 4;k++)
                                {
                                    if(k == 0 && A == sum[0])continue;
                                    if(k == 1 && B == sum[1])continue;
                                    if(k == 2 && C == sum[2])continue;
                                    if(k == 3 && D == sum[3])continue;
                                    dp[next[i][k]][st+bit[k]] = max(dp[next[i][k]][st+bit[k]],dp[i][st]+num[next[i][k]]);
                                }
                            }
                    }
        int ans = 0;
        int status = sum[0]*bit[0] + sum[1]*bit[1] + sum[2]*bit[2] + sum[3]*bit[3];
        for(int i = 0;i < cnt;i++)
            ans = max(ans,dp[i][status]);
        printf("Case %d: %d\n",cas++,ans);
    }
    return 0;
}

参考:http://blog.csdn.net/shllhsboa/article/details/16868565


  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.