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

AcWing275. 传纸条

AcWing275. 传纸条

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。

一次素质拓展活动中,班上同学安排坐成一个 mn 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。

幸运的是,他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标 (1,1),小轩坐在矩阵的右下角,坐标 (m,n)

从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。 

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。

班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙,反之亦然。 

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 0 表示),可以用一个 0∼100 的自然数来表示,数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度之和最大。

现在,请你帮助小渊和小轩找到这样的两条路径。

输入格式

第一行有 2 个用空格隔开的整数 mn,表示学生矩阵有 mn 列。

接下来的 m 行是一个 m×n 的矩阵,矩阵中第 ij 列的整数表示坐在第 i行 j列的学生的好心程度,每行的 n 个整数之间用空格隔开。

输出格式

输出一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围

1≤n,m≤50

输入样例:

3 3
0 3 9
2 8 5
5 7 0

输出样例:

34

难度:中等

时/空限制:1s / 64MB

总通过数:17039

总尝试数:36391

来源:《算法竞赛进阶指南》, NOIP2008提高组,Google面试题

算法标签 dp

这道题很像上一道题AcWing 1027. 方格取数 - AcWing。

AC代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int g[N][N];
int f[N * 2][N][N];
int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &g[i][j]);for (int k = 2; k <= n + m; k ++ )for (int i = max(1, k - m); i <= n && i < k; i ++ )for (int j = max(1, k - m); j <= n && j < k; j ++ )for (int a = 0; a <= 1; a ++ )for (int b = 0; b <= 1; b ++ ){int t = g[i][k - i];if (i != j || k == 2 || k == n + m) // 除了起点和终点之外,其余每个格子只能走一次{t += g[j][k - j];f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);}}printf("%d\n", f[n + m][n][n]);return 0;
}

相关文章:

AcWing275. 传纸条

AcWing275. 传纸条小渊和小轩是好朋友也是同班同学&#xff0c;他们在一起总有谈不完的话题。一次素质拓展活动中&#xff0c;班上同学安排坐成一个 m行 n 列的矩阵&#xff0c;而小渊和小轩被安排在矩阵对角线的两端&#xff0c;因此&#xff0c;他们就无法直接交谈了。幸运的…...

圆角矩形的绘制和曲线均匀化

摘要&#xff1a; 圆角矩形是软件 UI 等视觉设计中的常见表达&#xff0c;一种常见的绘制方法是将矩形的四角替换为与边相切的四分之一圆弧&#xff0c;然而这种绘制方式会在连接处产生视觉上的切折感&#xff0c;这是因为圆弧和直线的连接处只满足 G1G^1G1 连续性。本文探究了…...

【Linux】环境变量,命令行参数,main函数三个参数保姆教学

目录 ☃️1.奇奇怪怪的现象和孤儿进程 ☃️2.环境变量 ☃️3.深刻理解main函数的前两个参数和命令行参数 ☃️1.奇奇怪怪的现象和孤儿进程 首先回顾一下之前我们学过的fork&#xff08;&#xff09;创建子进程 fork(void)的返回值有两种 注意fork&#xff08;&#xff09;头…...

美国访问学者生活中有哪些饮食文化特点?

美国的教育毋庸置疑&#xff0c;排在世界数一数二的位置&#xff0c;美食美景更是数不胜数&#xff0c;那么他们有哪些饮食习惯&#xff0c;下面51访学网小编为你们详细介绍这些内容吧。 一、美国饮食文化特点 1、美国的饮食文化体现科学、适度、快捷&#xff0c;以满足人体的…...

RxJava中的Subject

要使用Rxjava首先要导入两个包&#xff0c;其中rxandroid是rxjava在android中的扩展 implementation io.reactivex:rxandroid:1.2.1implementation io.reactivex:rxjava:1.2.0Subject Subject 既可以是一个 Observer 也可以是一个 Observerable&#xff0c;它是连接 Observer 和…...

vue-element-admin在git 上 clone 之后无法install

一. 无法install的原因因为vue-element-admin引入的富文本编辑插件所导致 由于tui-editor变更 名字 导致 依赖查询找不到对应的版本二. 解决的办法先删掉package.json中tui-editor:1.3.3找到 \src\components\MarkdownEditor\index.vue 把所有的import 替换成下面4个import cod…...

Linux线程调度实验

Linux线程调度实验 1.获取线程属性 #include <stdio.h> #include <sys/types.h> #include <unistd.h> #include <pthread.h> #include <time.h> #include <stdlib.h> #include <errno.h> #define _GNU_SOURCE#define handle_error…...

洛谷P5735 【深基7.例1】距离函数 C语言/C++

【深基7.例1】距离函数 题目描述 给出平面坐标上不在一条直线上三个点坐标 (x1,y1),(x2,y2),(x3,y3)(x_1,y_1),(x_2,y_2),(x_3,y_3)(x1​,y1​),(x2​,y2​),(x3​,y3​)&#xff0c;坐标值是实数&#xff0c;且绝对值不超过 100.00&#xff0c;求围成的三角形周长。保留两位…...

企业什么要建设自有即时通讯软件系统

随着科技的不断发展&#xff0c;各种即时通讯软件也不断发展进步&#xff0c;而这也与企业的发展息息相关&#xff0c;因为每个人&#xff0c;每个企业都有属于自己的机密&#xff0c;属于自己的隐私。 钉钉&#xff0c;企业微信&#xff0c;等公有的即时通讯软件给企业带来便利…...

LocalDNS

目录 文章目录目录本节实战DNS优化1、dns 5s 超时问题解决办法2、NodeLocal DNSCache实验软件关于我最后本节实战 实战名称&#x1f498; 实战&#xff1a;NodeLocal DNSCache-2022.7.30(测试成功)&#x1f498; 实战&#xff1a;NodeLocal DNSCache-2023.2.21(测试成功) DNS优…...

线程池种类和拒绝策略

1、newCachedThreadPool()&#xff1a;可缓存的线程池&#xff0c;核心线程数量为0&#xff0c;最大线程数量为INT_MAX。线程空闲时间超过60秒被回收。适合处理大量小任务。 2、newFixedThreadPool()。固定线程个数的线程池&#xff0c;线程都是核心线程&#xff0c;没有应急线…...

Python制作9行最简单音乐播放器?不,我不满足

嗨害大家好鸭~我是小熊猫 好久不见啦~这次就来给大家整个大福利 ~ 源码资料电子书:点击此处跳转文末名片获取 最简单的9行代码音乐播放器如下&#xff1a; import time import pygamefile r歌曲路径 pygame.mixer.init() print(正在播放,file) track pygame.mixer.music.lo…...

零基础小白如何学会数据分析?

随着数字经济、大数据时代的发展&#xff0c;数据已然成为当下时代最重要的盈利资源&#xff0c;让企业在做决策和计划方案时更有针对性和依据&#xff0c;能提前预测市场发展方向&#xff0c;做好布局。由此而产生的数据分析岗位也逐渐被更多企业重视&#xff0c;特别是中大型…...

【Linux】vim的使用及常用快捷键(不会使用vim?有这篇文章就够了)

&#x1f525;&#x1f525; 欢迎来到小林的博客&#xff01;&#xff01;       &#x1f6f0;️博客主页&#xff1a;✈️小林爱敲代码       &#x1f6f0;️欢迎关注&#xff1a;&#x1f44d;点赞&#x1f64c;收藏✍️留言 目录&#x1f496;vim的基本概念vi…...

刷完这19道leetcode二分查找算法,不信进不了大厂

对于二分题&#xff0c;其实就是设定一个中间值 mid, 然后通过这个值进行一个判断 check(mid)&#xff0c; 通过这个函数的返回值&#xff0c;判断将不可能的一半剪切掉&#xff1b; 在刷题的时候需要注意主要是两部分&#xff0c;check 函数的定义以及边界的选择&#xff08;…...

四、Plugin Request and Sometimes pads

Request and Sometimes pads 到目前为止&#xff0c;我们只处理了总是可用的pad。然而&#xff0c;也有一些pad仅在某些情况下创建&#xff0c;或者仅在应用程序请求pad时创建。第一个有时被称为a;第二个被称为请求pad。pad的可用性(always, sometimes or request)可以在pad的…...

唤醒手腕 Java 后端 Springboot 结合 Redis 数据库学习笔记(更新中)

Redis 基本介绍 Redis Introduction The open source, in-memory data store used by millions of developers as a database, cache, streaming engine, and message broker. 基本概念&#xff1a;redis 是一个开源的、使用 C 语言编写的、支持网络交互的、可基于内存也可持…...

robotiq 2f 140安装在UR3机械臂后面在gazebo仿真中散架、抖动

robotiq 2f 140安装在UR3机械臂后面在gazebo仿真中散架、抖动 搭建环境&#xff1a; ubuntu: 20.04 ros: Nonetic sensor: robotiq_ft300 gripper: robotiq_2f_140_gripper UR: UR3 通过上一篇博客配置好ur3、力传感器和robotiq夹爪的gazebo仿真环境后&#xff0c;夹爪看起来…...

坐标系概念 四元数 欧拉角

1、四个概念&#xff1a;“地理”坐标系、“机体”坐标系、他们之间换算公式、换算公式用的系数。地理坐标系&#xff1a;东、北、天&#xff0c;以下简称地理。在这个坐标系里有重力永远是&#xff08;0,0,1g&#xff09;&#xff0c;地磁永远是&#xff08;0,1,x&#xff09;…...

从0开始写Vue项目-SpringBoot整合Mybatis-plus实现登录、注册功能

1.从0开始写Vue项目-环境和项目搭建_慕言要努力的博客-CSDN博客 2. 从0开始写Vue项目-Vue2集成Element-ui和后台主体框架搭建_慕言要努力的博客-CSDN博客 3. 从0开始写Vue项目-Vue页面主体布局和登录、注册页面_慕言要努力的博客-CSDN博客 一、前言 在之前我们以及搭建好了基…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

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/ # 主应用&…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...