HDU 1080 DP

HDU 1080 DP

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

匹配两个人相似度。

A,G,C。T。每两个都会有一个相应的值,给出两串基因。长度能够不一样,能够在基因中间加_使两串长度一样。然后有一个相应值。求最大相应值。

先做出相应的表

DP方程:

x=dp[i-1][j-1]+hash[str_a[i-1]][str_b[j-1]];
y=dp[i-1][j]+hash[str_a[i-1]][‘-‘];
z=dp[i][j-1]+hash[str_b[j-1]][‘-‘];
p[i][j]=Max(x,y,z);

#include "stdio.h"
#include "string.h"

int Max(int a,int b,int c)
{
    int x;
    x=a;
    if (b>x) x=b;
    if (c>x) x=c;
    return x;
}
int main()
{
    int Case,len_a,len_b,x,y,z,i,j;
    int dp[110][110],hash[210][210];
    char str_a[110],str_b[110];

    hash['A']['A']=hash['C']['C']=hash['T']['T']=hash['G']['G']=5;
    hash['A']['C']=hash['C']['A']=hash['A']['T']=hash['T']['A']=hash['-']['T']=hash['T']['-']=-1;
    hash['A']['G']=hash['G']['A']=hash['C']['T']=hash['T']['C']=hash['G']['T']=hash['T']['G']=hash['-']['G']=hash['G']['-']=-2;
    hash['A']['-']=hash['-']['A']=hash['C']['G']=hash['G']['C']=-3;
    hash['C']['-']=hash['-']['C']=-4;

    scanf("%d",&Case);
    while (Case--)
    {
        scanf("%d%s%d%s",&len_a,str_a,&len_b,str_b);

    //    memset(dp,0,sizeof(dp));
        dp[0][0]=0;
        for (i=1;i<=len_a;i++)
            dp[i][0]=dp[i-1][0]+hash['-'][str_a[i-1]];
        for (i=1;i<=len_b;i++)
            dp[0][i]=dp[0][i-1]+hash['-'][str_b[i-1]];

        for (i=1;i<=len_a;i++)
            for (j=1;j<=len_b;j++)
            {
                x=dp[i-1][j-1]+hash[str_a[i-1]][str_b[j-1]];
                y=dp[i-1][j]+hash[str_a[i-1]]['-'];
                z=dp[i][j-1]+hash[str_b[j-1]]['-'];
                dp[i][j]=Max(x,y,z);
            }
        printf("%d\n",dp[len_a][len_b]);
    }
    return 0;
}

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

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/115445.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • WPA2 KRACK Attacks 原文转载翻译[通俗易懂]

    WPA2 KRACK Attacks 原文转载翻译[通俗易懂]写在前面:博主水平有限,翻译中如果出现错误,还希望大家能够指正。原文链接:https://www.krackattacks.com/KeyReinstallationAttacks(krack)key重装攻击简介我们发现了关于WPA2的重大漏洞,WPA2是一个确保所有现代无线网络被保护的协议。当攻击者在受害者的一定范围内就可以利用这些漏洞来使用KRACK攻击。具体地说,攻

    2022年5月1日
    64
  • JavaScript中的document.cookie的使用

    JavaScript中的document.cookie的使用 我们已经知道,在document对象中有一个cookie属性。但是Cookie又是什么?“某些Web站点在您的硬盘上用很小的文本文件存储了一些信息,这些文件就称为Cookie。”——MSIE帮助。一般来说,Cookies是CGI或类似,比HTML高级的文件、程序等创建的,但是javascript也提供了对Cookies的很全面的访问权利。  我们先要学

    2022年7月27日
    4
  • 使用kong时报 validate.nginx.ingress.kubernetes.io 错误解决办法

    使用kong时报 validate.nginx.ingress.kubernetes.io 错误解决办法

    2021年5月14日
    171
  • startActivityForResult解析

    startActivityForResult解析startActivity用于页面间的正常跳转。startActivityForResult用于页面间的跳转并回传数据,比如商城类的App下单时会有选择地址,选择之后地址更新。1.先用startActivityForResult方式启动一个页面 btn=(Button)findViewById(R.id.btn);btn.setOnClickListen

    2022年7月11日
    14
  • Spring JDBC StoredProcedure类示例

    Spring JDBC StoredProcedure类示例org.springframework.jdbc.core.StoredProcedure类是RDBMS存储过程的对象抽象的超类。这个类是抽象的,目的是让子类将提供一个用于调用的类型化方法,该方法委托给所提供的execute(java.lang.Object…)方法。继承的sql属性是RDBMS中存储过程的名称。使用到的Student表的结构如下-CREATETAB…

    2022年7月26日
    1
  • java8 groupingby_java8的groupingby

    java8 groupingby_java8的groupingby可能很多人特别是刚毕业的应届生多少都学过一点java8的东西,知道有很多的新特性但是在实用性上总感觉没地方用。。之前在找实习之前也学过一些东西,但是很快就因为没使用而忘光了这几天在项目中大量使用,才得以回想起来:这次主要说groupingby,在项目中往往会因为查询效率的问题而批量查询某些DO,但是在批量查询之后是需要对查询到的list进行归类的,比如一个DO类person,里面包含年龄,性别等属…

    2022年8月20日
    5

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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