[NOIP2007]矩阵取数游戏
点我写题
题目描述
帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下:
1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素;
2.每次取走的各个元素只能是该元素所在行的行首或行尾;
3.每次取数都有一个得分值,为每行取数的得分之和,每行取数的得分 = 被取走的元素值 * 2i,其中i表示第i次取数(从1开始编号);
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序,对于任意矩阵,可以求出取数后的最大得分。
示例1
输入
复制
2 3 1 2 3 4 2
输出
复制
82
思路:容易观察到,每列可以单独考虑,即局部最优解能构成全局最优解,设dp[i][t][k]表示,n*m的矩阵中,第i行元素,到第t轮选元素,前面选了k个的最大值。
转移:考虑当前轮是选前面的还是选后面的,选前面的,就是dp[i][t][k]=dp[i][t-1][k-1]+a[k]*(2^t),选后面的dp[i][t][k]=dp[i][t-1][k]+a[m-(t-k)+1]*(2^t)(即前面选k个后面就该选了t-k个了)。
ps:这里还硬缝合了个高精度,但是java用BigInteger就能过,java果然是世界上最好的语言,(bushi~)。
纠错:牛客空间比较大三维dp能过,但是洛谷只能俩维,把没用的那维去掉就好了然后加个初始化。
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner s=new Scanner(System.in);int n=s.nextInt(),m=s.nextInt();int a[][]=new int [n+10][m+10];BigInteger mul[]=new BigInteger [m+10];mul[0]=BigInteger.valueOf(1);for(int i=1;i<=m;i++) mul[i]=mul[i-1].multiply(BigInteger.valueOf(2));for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {a[i][j]=s.nextInt();}}BigInteger ans=BigInteger.valueOf(0);for(int i=1;i<=n;i++) {BigInteger res=BigInteger.valueOf(0);BigInteger dp[][]=new BigInteger [m+10][m+10];for(int j=0;j<=m;j++) {for(int k=0;k<=m;k++) {dp[j][k]=new BigInteger("0");}}for(int t=1;t<=m;t++) {for(int j=0;j<=t;j++) {dp[t][j]=dp[t-1][j].add(BigInteger.valueOf(a[i][m-(t-j)+1]).multiply(mul[t]));if(j>0) {BigInteger x=dp[t-1][j-1].add(mul[t].multiply(BigInteger.valueOf(a[i][j])));if(dp[t][j].compareTo(x)<0) dp[t][j]=x;}if(res.compareTo(dp[t][j])<0) res=dp[t][j];}}ans=ans.add(res);}System.out.print(ans+"\n");}}
相关文章:
[NOIP2007]矩阵取数游戏
点我写题 题目描述 帅帅经常跟同学玩一个矩阵取数游戏:对于一个给定的n*m的矩阵,矩阵中的每个元素aij均为非负整数。游戏规则如下: 1.每次取数时须从每行各取走一个元素,共n个。m次后取完矩阵所有元素; 2.每次取走的…...
在Linux系统上安装.NET
测试系统:openKylin(开放麒麟) 1.确定系统和架构信息: 打开终端(Ctrl Alt T),输入cat /etc/os-release查看系统版本相关信息。 输入uname -m查看系统架构。确保你的系统和架构符合.NET 的要求,如果架构…...
PCB Editor层叠文件(Gerber文件输出-01)
先看底层和表层,如下图 钢网表层和底层,如下图 丝印表层和底层,如下图 阻焊表层和底层,如下图 下面来添加钻孔层,先提取钻孔表 点击OK后钻孔表会挂在鼠标上...
labelimg闪退的解决办法
其实就是你的python版本太高不稳定不支持labelimg 标记时出现闪退 问题原因:python版本过高 解决方案 第一步: 在python3.9以上的版本运行软件会闪退,这个时候我们需要创建一个3.9或者及以下的虚拟环境 conda cr…...
【开源免费】基于Vue和SpringBoot的在线文档管理系统(附论文)
本文项目编号 T 038 ,文末自助获取源码 \color{red}{T038,文末自助获取源码} T038,文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...
数据库管理-第287期 Oracle DB 23.7新特性一览(20250124)
数据库管理287期 20245-01-24 数据库管理-第287期 Oracle DB 23.7新特性一览(20250124)1 AI向量搜索:算术和聚合运算2 更改Compatible至23.6.0,以使用23.6或更高版本中的新AI向量搜索功能3 Cloud Developer包4 DBMS_DEVELOPER.GET…...
Golang :用Redis构建高效灵活的应用程序
在当前的应用程序开发中,高效的数据存储和检索的必要性已经变得至关重要。Redis是一个快速的、开源的、内存中的数据结构存储,为各种应用场景提供了可靠的解决方案。在这个完整的指南中,我们将学习什么是Redis,通过Docker Compose…...
四层网络模型
互联网由终端主机、链路和路由器组成,数据通过逐跳的方式,依次经过每条链路进行传输。 网络层的工作是将数据包从源端到目的端,跨越整个互联网。 网络层的数据包称为数据报。网络将数据报交给链路层,指示它通过第一条链路发送数据…...
CUDA学习-内存访问
一 访存合并 1.1 说明 本部分内容主要参考: 搞懂 CUDA Shared Memory 上的 bank conflicts 和向量化指令(LDS.128 / float4)的访存特点 - 知乎 1.2 share memory结构 图1.1 share memory结构 放在 shared memory 中的数据是以 4 bytes(即 32 bits)作为 1 个 word,依…...
进程通讯——类型和发展
进程常用交互方法如上...
在 Windows 11 中为 SMB 3.x 文件共享协议提供 RDMA 支持
注:机翻,未校。 Enable SMB Direct in Windows 11 在 Windows 11 中启用 SMB Direct Provides RDMA support for the SMB 3.x file sharing protocol 为 SMB 3.x 文件共享协议提供 RDMA 支持 Vigneshwaran Vijayakumar November 3, 2024 Last Updat…...
C 标准库 - `<errno.h>`
C 标准库 - <errno.h> 引言 在C语言编程中,正确处理错误是保证程序稳定性和可靠性的关键。C标准库中的<errno.h>头文件提供了错误码定义和宏,使得开发者能够更好地管理和处理程序运行过程中可能出现的错误。本文将详细介绍<errno.h>头文件的作用、常用错…...
2025年01月28日Github流行趋势
项目名称:maybe 项目地址url:https://github.com/maybe-finance/maybe项目语言:Ruby历史star数:37540今日star数:1004项目维护者:zachgoll, apps/dependabot, tmyracle, Shpigford, crnsh项目简介ÿ…...
7. 马科维茨资产组合模型+金融研报AI长文本智能体(Qwen-Long)增强方案(理论+Python实战)
目录 0. 承前1. 深度金融研报准备2. 核心AI函数代码讲解2.1 函数概述2.2 输入参数2.3 主要流程2.4 异常处理2.5 清理工作2.7 get_ai_weights函数汇总 3. 汇总代码4. 反思4.1 不足之处4.2 提升思路 5. 启后 0. 承前 本篇博文是对前两篇文章,链接: 5. 马科维茨资产组…...
Android 启动流程
一 Bootloader 在嵌入式系统中,Bootloader的引导过程与传统的PC环境有所不同,主要是因为嵌入式系统的硬件配置和应用场景更加多样化。以下是嵌入式系统中Bootloader被引导的一般流程: 1. 硬件复位 当嵌入式设备上电或复位时,处…...
庆祝2025到来:C++编程的新篇章
作者:w(゚Д゚)w吓洗宝宝了 发布时间:2025年1月19日00:00 引言 新年伊始,万象更新。在这充满希望的2025年,我们迎来了新的机遇和挑战。作为C编程爱好者的一员,我感到无比激动和自豪。C作为一种强…...
基于STM32的智能家用温控器设计
目录 引言系统设计 硬件设计软件设计 系统功能模块 温度监测模块自动加热与制冷模块用户交互与显示模块节能模式与定时功能模块远程控制与数据上传模块 控制算法 温度调节算法定时任务与节能优化算法数据记录与反馈算法 代码实现 温度监测与自动控制代码定时与节能模式代码数据…...
扣子平台音频功能:让声音也能“智能”起来。扣子免费系列教程(14)
在数字化时代,音频内容的重要性不言而喻。无论是在线课程、有声读物,还是各种多媒体应用,音频都是传递信息、增强体验的关键元素。扣子平台的音频功能,为开发者和内容创作者提供了一个强大而灵活的工具,让音频的使用和…...
Dismissible组件的用法
文章目录 1 概念介绍2 使用方法3 示例代码我们在上一章回中介绍了GestureDetector Widget相关的内容,本章回中将介绍Dismissible Widget.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的Dismissible是一个事件响应Widget,它和GestureDetector类似,不过它只…...
C语言--数据在内存中的存储
在C语言中,数据在内存中的存储方式主要取决于数据的类型和存储位置。以下是C语言中数据在内存中的存储方式的详细说明: 1. 数据类型与存储方式 基本数据类型 • 整数类型(如int、short、long等): • 存储方式&#x…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
