当前位置: 首页 > news >正文

[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]矩阵取数游戏

点我写题 题目描述 帅帅经常跟同学玩一个矩阵取数游戏&#xff1a;对于一个给定的n*m的矩阵&#xff0c;矩阵中的每个元素aij均为非负整数。游戏规则如下&#xff1a; 1.每次取数时须从每行各取走一个元素&#xff0c;共n个。m次后取完矩阵所有元素&#xff1b; 2.每次取走的…...

在Linux系统上安装.NET

测试系统&#xff1a;openKylin(开放麒麟) 1.确定系统和架构信息&#xff1a; 打开终端&#xff08;Ctrl Alt T&#xff09;&#xff0c;输入cat /etc/os-release查看系统版本相关信息。 输入uname -m查看系统架构。确保你的系统和架构符合.NET 的要求&#xff0c;如果架构…...

PCB Editor层叠文件(Gerber文件输出-01)

先看底层和表层,如下图 钢网表层和底层,如下图 丝印表层和底层,如下图 阻焊表层和底层,如下图 下面来添加钻孔层,先提取钻孔表 点击OK后钻孔表会挂在鼠标上...

labelimg闪退的解决办法

其实就是你的python版本太高不稳定不支持labelimg 标记时出现闪退 问题原因&#xff1a;python版本过高 解决方案 第一步&#xff1a; 在python3.9以上的版本运行软件会闪退&#xff0c;这个时候我们需要创建一个3.9或者及以下的虚拟环境 conda cr…...

【开源免费】基于Vue和SpringBoot的在线文档管理系统(附论文)

本文项目编号 T 038 &#xff0c;文末自助获取源码 \color{red}{T038&#xff0c;文末自助获取源码} T038&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析 六、核心代码6.1 查…...

数据库管理-第287期 Oracle DB 23.7新特性一览(20250124)

数据库管理287期 20245-01-24 数据库管理-第287期 Oracle DB 23.7新特性一览&#xff08;20250124&#xff09;1 AI向量搜索&#xff1a;算术和聚合运算2 更改Compatible至23.6.0&#xff0c;以使用23.6或更高版本中的新AI向量搜索功能3 Cloud Developer包4 DBMS_DEVELOPER.GET…...

Golang :用Redis构建高效灵活的应用程序

在当前的应用程序开发中&#xff0c;高效的数据存储和检索的必要性已经变得至关重要。Redis是一个快速的、开源的、内存中的数据结构存储&#xff0c;为各种应用场景提供了可靠的解决方案。在这个完整的指南中&#xff0c;我们将学习什么是Redis&#xff0c;通过Docker Compose…...

四层网络模型

互联网由终端主机、链路和路由器组成&#xff0c;数据通过逐跳的方式&#xff0c;依次经过每条链路进行传输。 网络层的工作是将数据包从源端到目的端&#xff0c;跨越整个互联网。 网络层的数据包称为数据报。网络将数据报交给链路层&#xff0c;指示它通过第一条链路发送数据…...

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 支持

注&#xff1a;机翻&#xff0c;未校。 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流行趋势

项目名称&#xff1a;maybe 项目地址url&#xff1a;https://github.com/maybe-finance/maybe项目语言&#xff1a;Ruby历史star数&#xff1a;37540今日star数&#xff1a;1004项目维护者&#xff1a;zachgoll, apps/dependabot, tmyracle, Shpigford, crnsh项目简介&#xff…...

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. 承前 本篇博文是对前两篇文章&#xff0c;链接: 5. 马科维茨资产组…...

Android 启动流程

一 Bootloader 在嵌入式系统中&#xff0c;Bootloader的引导过程与传统的PC环境有所不同&#xff0c;主要是因为嵌入式系统的硬件配置和应用场景更加多样化。以下是嵌入式系统中Bootloader被引导的一般流程&#xff1a; 1. 硬件复位 当嵌入式设备上电或复位时&#xff0c;处…...

庆祝2025到来:C++编程的新篇章

作者&#xff1a;w(&#xff9f;Д&#xff9f;)w吓洗宝宝了 发布时间&#xff1a;2025年1月19日00:00 引言 新年伊始&#xff0c;万象更新。在这充满希望的2025年&#xff0c;我们迎来了新的机遇和挑战。作为C编程爱好者的一员&#xff0c;我感到无比激动和自豪。C作为一种强…...

基于STM32的智能家用温控器设计

目录 引言系统设计 硬件设计软件设计 系统功能模块 温度监测模块自动加热与制冷模块用户交互与显示模块节能模式与定时功能模块远程控制与数据上传模块 控制算法 温度调节算法定时任务与节能优化算法数据记录与反馈算法 代码实现 温度监测与自动控制代码定时与节能模式代码数据…...

扣子平台音频功能:让声音也能“智能”起来。扣子免费系列教程(14)

在数字化时代&#xff0c;音频内容的重要性不言而喻。无论是在线课程、有声读物&#xff0c;还是各种多媒体应用&#xff0c;音频都是传递信息、增强体验的关键元素。扣子平台的音频功能&#xff0c;为开发者和内容创作者提供了一个强大而灵活的工具&#xff0c;让音频的使用和…...

Dismissible组件的用法

文章目录 1 概念介绍2 使用方法3 示例代码我们在上一章回中介绍了GestureDetector Widget相关的内容,本章回中将介绍Dismissible Widget.闲话休提,让我们一起Talk Flutter吧。 1 概念介绍 我们在这里介绍的Dismissible是一个事件响应Widget,它和GestureDetector类似,不过它只…...

C语言--数据在内存中的存储

在C语言中&#xff0c;数据在内存中的存储方式主要取决于数据的类型和存储位置。以下是C语言中数据在内存中的存储方式的详细说明&#xff1a; 1. 数据类型与存储方式 基本数据类型 • 整数类型&#xff08;如int、short、long等&#xff09;&#xff1a; • 存储方式&#x…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

GraphQL 实战篇:Apollo Client 配置与缓存

GraphQL 实战篇&#xff1a;Apollo Client 配置与缓存 上一篇&#xff1a;GraphQL 入门篇&#xff1a;基础查询语法 依旧和上一篇的笔记一样&#xff0c;主实操&#xff0c;没啥过多的细节讲解&#xff0c;代码具体在&#xff1a; https://github.com/GoldenaArcher/graphql…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...