ACM/ICPC2014鞍山现场赛E hdu5074Hatsune Miku「建议收藏」

ACM/ICPC2014鞍山现场赛E hdu5074Hatsune Miku

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

题目链接:题意:

给定一个m*m的矩阵mp。然后给定一个长度为n的序列

sum= mp[a[1]][a[2]]+……+mp[a[n-1]][a[n]];

假设a[i]小于0的话则a[i]能够为1~m之间的随意一个数,求sum的最大值

我们能够枚举第i个位置

然后dp[i][j]=max(dp[i][j],dp[i-1][k]+mp[k][j]) 表示第i个位置在j的最大值;

然后分两种情况

假设a[i]是一个确定的数的话 dp[i][a[i]]=max( dp[i][a[i]],dp[i-1][j]+mp[j][a[i]] )

假设不确定的话 就仅仅能枚举a[i]了 dp[i][k]=max(dp[i][k],dp[i-1][j]+mp[j][k]);

这两种情况都是建立在前一个位置已经确定了值的情况下;

代码例如以下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 55;
int mp[maxn][maxn];
int dp[maxn*2][maxn],a[maxn*2];

int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++)
                scanf("%d",&mp[i][j]);
        }
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        memset(dp,-1,sizeof(dp));
        if(a[1]!=-1)
            dp[1][a[1]]=0;
        else
            for(int i=1;i<=m;i++)
                dp[1][i]=0;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(dp[i-1][j]!=-1){//假设前一项已经确定
                    if(a[i]!=-1)
                        dp[i][a[i]]=max(dp[i][a[i]],dp[i-1][j]+mp[j][a[i]]);
                    else{
                        for(int k=1;k<=m;k++)
                            dp[i][k]=max(dp[i][k],dp[i-1][j]+mp[j][k]);
                    }
                }
            }
        }
        /***************
        cout<<"   debug   "<<endl;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=m;j++)
                cout<<dp[i][j]<<" ";
            cout<<endl;
        }
        cout<<"***********"<<endl;
        **************/
        int maxn = -1000;
        for(int i=1;i<=m;i++)
            maxn=max(dp[n][i],maxn);
        printf("%d\n",maxn);
    }
    return 0;
}

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

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

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

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

(0)


相关推荐

  • 【移动端】手机界面的设计尺寸

    【移动端】手机界面的设计尺寸从设计方面来看,做手机界面设计的尺寸一般分为iPhone和Android两种设备。iPhone的分辨率设备 逻辑分辨率(point)(pt) 物理分辨率(pixel)(px) 屏幕尺寸 缩放因子(scale) 像素密度PPI 比例(近似) iPhone2G/3/3GS 320×480 320×480 3.5寸 @1x 163 2:3 iPhone4/4S 320×480 640..

  • 深入浅出python 百度网盘_python的算法有哪些

    深入浅出python 百度网盘_python的算法有哪些关于sharingyourcode问题按照书上面的步骤,首先prepareyourdisribution创建了一个名为nester的文件夹,在文件夹中创建了nester.py和setup.py两个文件。按照步骤接下来Buildadistributionfile-》InstallyourdistributionintoyourlocalcopyofPyth

    2022年10月17日
  • 阿里笔试_阿里在线测评重不重要

    阿里笔试_阿里在线测评重不重要阿里笔试

  • oracle导出建表sql_Oracle数据库语句汇总

    oracle导出建表sql_Oracle数据库语句汇总第一步:安装pl/sqlDeveloper(此程序Oracle必备软件,在此不再讨论)第二步:登录pl/sqlDeveloper                                           登录界面第三步在左侧菜单选择Tables第三步点开Tables后在要导出的表上右键-DBMS_MetaData-DDL即可导出创建表的DDL语句

  • 在IDEA中实战Git「建议收藏」

    在IDEA中实战Git「建议收藏」工作中多人使用版本控制软件协作开发,常见的应用场景归纳如下:假设小组中有两个人,组长小张,组员小袁场景一:小张创建项目并提交到远程Git仓库场景二:小袁从远程Git仓库上获取项目源码场景三:小袁修改了部分源码,提交到远程仓库场景四:小张从远程仓库获取小袁的提交场景五:小袁接受了一个新功能的任务,创建了一个分支并在分支上开发场景六:小袁把分支提交到远程Git仓库场景七…

  • html echarts饼状图_echarts环形图

    html echarts饼状图_echarts环形图ECharts旭日图旭日图(Sunburst)由多层的环形图组成,在数据结构上,内圈是外圈的父节点。因此,它既能像饼图一样表现局部和整体的占比,又能像矩形树图一样表现层级关系。ECharts创建旭日图很简单,只需要在series配置项中声明类型为sunburst即可,data数据结构以树形结构声明,看下一个简单的实例:实例varoption={series:{type:’s…

发表回复

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

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