HDU P3341 Lost’s revenge 题解+数据生成器

HDU P3341 Lost’s revenge 题解+数据生成器LostandAekdyCoinarefriends.Theyalwaysplay”numbergame”(Aboringgamebasedonnumbertheory)together.WeallknowthatAekdyCoinisthemancalled”nuclearweaponofFZU,descendantofJi…

大家好,又见面了,我是你们的朋友全栈君。

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.

              ——by HDU;

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



就是,有N个由’A’C’G’T’构成的KEY串,给一个可以改变顺序的word串,求最多匹配(KEY可重复使用)

AC自动机+DP

f[i][num0][num1][num2][num3]

表示当前在AC自动机i点,’A’用了num0个,’C’用了num1个……

于是她可以转移到她的所有子节点及子节点的fail链上

但是显然因为num0~3他们的范围的问题(你只能每个都开到word串的长这么大,就是40),这样会MLE(自己算算咯)

发现数组开的很冗余;

于是考虑状态压缩(还是hash???)

反正把num0~num3压到数组的一维里,对num0而言每个1在压缩后为该维贡献1(sum0=1),对num1而言每个1在压缩后则为该维贡献1*(num0+1)(sum1=num0+1),对num1而言每个1在压缩后则为该维贡献1*(num1+1)*sum1(sum2=(num1+1)*sum1)…….

这样把原状态的后4维按权(sum)压到一维里

可以看出,这样压缩后不会有多余的空间;

那么开出的数组就是点数i*(num0+1)*(num1+1)*(num2+1)*(num3+1)(组合数学吧)

最大也就num0~3均取10——也不是很大呢

代码如下:

  1 #include<cstdio>
  2 #include<cstring>
  3 using namespace std;
  4 struct ss{
  5     int ch[4];
  6 }x[1000];
  7 int n,tot;
  8 int is_end[510],fail[510];
  9 int que[1000000];
 10 char key[15],word[45];
 11 int num[4],sum[4],f[510][15001];
 12 int boo(int ,int ,int ,int ,int );
 13 void bfs_fail();
 14 int dp();
 15 int pd(char );
 16 int main(){
 17     int i,j,k,len,T=0;
 18     while(1){
 19         scanf("%d",&n);
 20         if(!n)
 21             return 0;
 22         tot=0;
 23         memset(is_end,0,sizeof(is_end));
 24         memset(fail,0,sizeof(fail));
 25         memset(x,0,sizeof(x));
 26         for(i=0;i<=3;i++)
 27             num[i]=0,sum[i]=0;
 28         for(i=1;i<=n;i++){
 29             scanf("%s",key);
 30             len=strlen(key)-1;k=0;
 31             for(j=0;j<=len;j++){
 32                 if(!x[k].ch[pd(key[j])])
 33                     x[k].ch[pd(key[j])]=++tot;
 34                 k=x[k].ch[pd(key[j])];
 35             }
 36             is_end[k]++;
 37         }
 38         bfs_fail();
 39         scanf("%s",word);len=strlen(word)-1;
 40         for(i=0;i<=len;i++)
 41             num[pd(word[i])]++;
 42         sum[0]=1;
 43         for(i=1;i<=3;i++)sum[i]=sum[i-1]*(num[i-1]+1);
 44         printf("Case %d: %d\n",++T,dp());
 45     }
 46     return 0;
 47 }
 48 int boo(int i,int j,int k,int l,int p){
 49     int x;
 50     switch (p){
 51         case 0:x=i;break;
 52         case 1:x=j;break;
 53         case 2:x=k;break;
 54         case 3:x=l;break;
 55     }
 56     if(num[p]-x-1>=0)
 57         return 1;
 58     return 0;
 59 }
 60 void bfs_fail(){
 61     int h=0,t=1,i,j,k;
 62     while(h<t){
 63         ++h;
 64         for(i=0;i<=3;i++)
 65             if(x[que[h]].ch[i]){
 66                 j=que[h];
 67                 while(1){
 68                     if(x[j].ch[i]&&j!=que[h]){
 69                         fail[x[que[h]].ch[i]]=x[j].ch[i];
 70                         break;
 71                     }
 72                     else{
 73                         if(!j)
 74                             break;
 75                         j=fail[j];
 76                     }
 77                 }
 78                 que[++t]=x[que[h]].ch[i];
 79             }
 80     }
 81 }
 82 int dp(){
 83     memset(f,-1,sizeof(f));f[0][0]=0;
 84     int i,j,k,l,o,p,q,r,ans=-1;
 85     for(i=0;i<=num[0];i++)
 86         for(j=0;j<=num[1];j++)
 87             for(k=0;k<=num[2];k++)
 88                 for(l=0;l<=num[3];l++)
 89                     for(o=0;o<=tot;o++)
 90                         if(f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]!=-1)
 91                             for(p=0;p<=3;p++)
 92                                 if(x[o].ch[p]&&boo(i,j,k,l,p)){
 93                                     r=x[o].ch[p];q=0;
 94                                     while(r){
 95                                         q+=is_end[r];
 96                                         r=fail[r];
 97                                     }
 98                                     r=x[o].ch[p];
 99                                     while(1){
100                                         f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]=f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]>f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]+q?f[r][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]+sum[p]]:f[o][i*sum[0]+j*sum[1]+k*sum[2]+l*sum[3]]+q;
101                                         if(!r)break;
102                                         r=fail[r];
103                                     }
104                                 }
105     q=sum[0]*num[0]+sum[1]*num[1]+sum[2]*num[2]+sum[3]*num[3];
106     for(i=0;i<=tot;i++)
107         for(j=0;j<=q;j++)
108             if(ans<f[i][j])
109                 ans=f[i][j];
110     return ans;
111 }
112 int pd(char a){
113     int i;
114     switch (a) {
115         case 'A':i=0;break;
116         case 'C':i=1;break;
117         case 'G':i=2;break;
118         case 'T':i=3;break;
119     }
120     return i;
121 }

由于本人也在这个题上卡了好久,故放上数据生成器:

HDU P3341 Lost's revenge 题解+数据生成器
HDU P3341 Lost's revenge 题解+数据生成器

#include<cstdio>
#include<cstring>
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
char s[4]={
    
    'A','C','G','T'};
int main()
{
    freopen("input.txt","w",stdout);
    srand(time(0));
    int T=50,n,l;
    for(int i=1;i<=T;i++){
        n=rand()%5+1;
        printf("%d\n",n);
        for(int j=1;j<=n;j++){
            l=rand()%5+1;
            for(int k=1;k<=l;k++)
                printf("%c",s[rand()%4]);
            printf("\0");printf("\n");
        }
        l=rand()%20+1;
            for(int k=1;k<=l;k++)
                printf("%c",s[rand()%4]);
            printf("\0");printf("\n");
    }
    printf("0");
}

data

祝AC

 

转载于:https://www.cnblogs.com/nietzsche-oier/p/6476022.html

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

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

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

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

(0)


相关推荐

  • loadrunner11激活成功教程技巧

    loadrunner11激活成功教程技巧loadrunner11的激活成功教程步骤:1、用mlr5lprg.dll、lm70.dll覆盖LR11安装目录下“bin”文件夹中的对应文件。2、修改注册表,可以使用deletelicence工具删除,也可以手动删除。1)deletelicence工具删除很方便,记住以管理员身份运行,直接按照提示操作即可。2)手动修改注册表。开始-&amp;gt;运行-&amp;gt;regedit即可手动修改注册表。删除下面…

  • Oracle、plsql安装以及使用教程「建议收藏」

    Oracle、plsql安装以及使用教程「建议收藏」Oracle安装Oracle(11g)数据库安装详细图解教程plsql安装PLSQL下载、安装、配置、连接详细教程创建数据库注意略过关于监听配置的所有部分Oracle创建数据库实例plsql连接数据库如下所示,按照上述步骤完成安装创建之后,只需要在database前面加个127.0.0.1/你创建的数据库即可建表点击file->new->table之后根据需要创建数据库即可…

  • oracle 存储过程

    oracle 存储过程

  • Verilog hdl与VHDL混用详解

    Verilog hdl与VHDL混用详解Veriloghdl与VHDL混用详解1.概述由于在FPGA开发过程中,多人合作时可能遇到有人使用veriloghdl,有人遇到VHDL的情况,这就涉及到了veriloghdl与VHDL的相…

  • vuecli3配置webpack_vue不混淆如何配置

    vuecli3配置webpack_vue不混淆如何配置前言如果我们想在webpack中使用vue,就需要在webpack中配置vue配置vue首先,我们需要在项目中安装vue,安装命令如下:npminstallvue–save安装完成后

  • 角度和弧度之间的转换

    角度和弧度之间的转换在编程中,我们经常会用到角度或者弧度,但是往往我们所得到的不是角度就是弧度,需要转换一下才能用到,这里我总结了角度和弧度之间的转换,1、转换方法:角度转弧度π/180×角度弧度变角度180/π×弧度例:角度转弧度//其中a是最开始的角度,现在将它转换成弧度制a//4*atan(1.0)就是我们用到的圆周率π,不管角度还是弧度,都是double型voidCBa…

发表回复

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

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