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;
}

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

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

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

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

(0)


相关推荐

  • 均方误差与方差的区别_平均数 方差 标准差

    均方误差与方差的区别_平均数 方差 标准差一、百度百科上方差是这样定义的:看这么一段文字可能有些绕,那就先从公式入手,对于一组随机变量或者统计数据,其期望值我们由E(X)表示,即随机变量或统计数据的均值,然后对各个数据与均值的差的平方求和,最后对它们再求期望值就得到了方差公式。这个公式描述了随机变量或统计数据与均值的偏离程度。二、方差与标准差之间的关系就比较简单了根号里的内容就是我们刚提到的那么问题来了,

  • nginx和gateway什么关系_api网关和redis的关系

    nginx和gateway什么关系_api网关和redis的关系经常遇到别人问我,有了nginx做网关,为啥还要用到gateway呢首先这两种网关的定义不一样用户访问的总入口,也就是前端页面的容器,流量网关gateway的定义是针对每一个业务微服务来得,属于业务网关借鉴一个图对于具体的后端业务应用或者是服务和业务有一定关联性的策略网关就是上图左边的架构模型——业务网关。业务网关针对具体的业务需要提供特定的流控策略、缓存策略、鉴权认证策略等等。与业务网关相反,定义全局性的、跟具体的后端业务应用和服务完全无关的策略网关就是上图右边所示的架构模型

    2022年10月11日
  • android之bundle是什么_什么是bundle

    Bundle,是Android开发中的一个类,用于Activity之间传输数据用。Intent it = new Intent(A.this,B.class);Bundle bundle = new Bundle();bundle.putString(“name”,”张三”);it.putExtrats(bundle);startActivity(it);这样就把name为张三这个数据从A

  • JDK下载与安装教程(超详细)「建议收藏」

    JDK下载与安装教程(超详细)「建议收藏」JDK下载与安装教程(超详细)学习JAVA,必须得安装一下JDK(javadevelopmentkitjava开发工具包),配置一下环境就可以学习JAVA了,下面是下载和安装JDK的教程:1.JDK下载地址:[http://www.oracle.com/technetwork/java/javase/downloads/index.html]点开链接后选择如下下载按钮(选择的是jdk1.8的,也可以选择更高版本的。提示:最好创建一个Oracle账号,以便以后使用)2.点击下载后,会出现如下

  • 网站系统开发需要掌握的技术有哪些_网页开发需要学什么

    网站系统开发需要掌握的技术有哪些_网页开发需要学什么1、JDBC技术在JavaWeb应用开发中,数据库管理系统(RDBMS)的使用是不可缺少的。JDBC(JavaDatabaseConnectivity)是一种用于执行SQL语句的Ja

  • 使用Source Safe for SQL Server解决数据库版本管理问题(转载)

    使用Source Safe for SQL Server解决数据库版本管理问题(转载)

    2021年11月25日

发表回复

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

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