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)


相关推荐

  • 移植Linux_如何把Linux移植到手机

    移植Linux_如何把Linux移植到手机作者:liukun321(咕唧咕唧)原文出处:http://blog.csdn.net/liukun321关于linux移植出现了几个小问题,在此记录:1、下载yaffs2源码,给内核打完补丁后,编译出错。解决方法,下载与内核版本相匹配的yaffs2文件系统源码或下载

  • 基于pytorch卷积人脸表情识别–毕业设计「建议收藏」

    基于卷积神经网络的人脸表情识别前言毕业设计内容介绍卷积神经网络的设计卷积网络的模型卷积池化过程详细说明第一层卷积池化过程第二层卷积池化过程第三层卷积池化过程全连接层过程模型的训练过程卷积与池化原理模型如何训练模型的评估指标训练结果分析通过训练曲线分析通过混淆矩阵分析效果通过摄像头识别表情设计流程效果演示部分代码展示总结前言这篇文章记录一下我本科毕业设计的内容。我的课题是人脸表情识别,本来最开始按照历届学长的传统是采用MATLAB用传统的机器学习方法来实现分类的。但是鉴于我以前接触过一点点深度学习的内容,

  • 薪资涨幅30% 怎么算(如何把自己的薪资提高)

    列出薪金高于在部门30bySamWilliams通过山姆·威廉姆斯我如何在五个月内将薪金提高一倍并获得一份了不起的工作(HowIDoubledmySalaryinFiveMonthsandGotanAmazingJob)SixmonthsagoIquitmyjobasajuniorJavaScriptdeveloperandtrav…

  • 使用百度echarts制作可视化大屏——最终效果和动态数据刷新「建议收藏」

    使用百度echarts制作可视化大屏——最终效果和动态数据刷新「建议收藏」最终效果如下图:接下来就是数据动态刷新了,这个没什么好说的,就是一个$.post的事,传递一个json给自定义的resresh函数就行了。$.post(url,null,function(d){resresh(d);},’json’);总结下来,有以下一些心得:1、大屏里面,设计是第一位的;2、要言之有物;3、能…

    2022年10月12日
  • 2021年程序员平均工资_公司薪酬制度调查报告

    2021年程序员平均工资_公司薪酬制度调查报告根据中国互联网络信息中心(CNNIC)近日发布第47次《中国互联网络发展状况统计报告》。截至2020年12月,我国网民规模达9.89亿,较2020年3月增长8540万,互联网普及率达70.4%。截至2020年12月,我国在线教育、在线医疗用户规模分别为3.42亿、2.15亿,占网民整体的34.6%、21.7%。我国网上零售额达11.76万亿元,较2019年增长10.9%。其中,实物商品网上零售额9.76万亿元,占社会消费品零售总额的24.9%。截至2020年12月,我国网络购物用户规模达7.82亿,

    2022年10月11日
  • 安装计算机的显卡出现问题,电脑显卡驱动安装失败如何解决「建议收藏」

    安装计算机的显卡出现问题,电脑显卡驱动安装失败如何解决「建议收藏」部分的网友们是电脑重装新的系统后出现的,也有部分的网友们是用系统自带的显卡更新的功能程序导致的,要如何解决显卡驱动安装失败的问题呢?一般寻找原因所在,一般是驱动数字签名的问题引起的,或者是显卡驱动的型号下载的不对。下面小编整理了对此问题的解答。一起来看看显卡驱动安装失败的解决方法吧!法一;驱动数字签名导致的;(1)win+R快捷键打开运行窗口,输入gpedit.msc后点击确定。(2)打开组策略编…

发表回复

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

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