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

P1004 [NOIP2000 提高组] 方格取数

题目描述

设有 �×�N×N 的方格图 (�≤9)(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 00。如下图所示(见样例):


 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                         B 

某人从图的左上角的 �A 点出发,可以向下行走,也可以向右走,直到到达右下角的 �B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 00)。
此人从 �A 点到 �B 点共走两次,试找出 22 条这样的路径,使得取得的数之和为最大。

输入格式

输入的第一行为一个整数 �N(表示 �×�N×N 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 00 表示输入结束。

输出格式

只需输出一个整数,表示 22 条路径上取得的最大的和。

输入输出样例

输入 #1复制

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

输出 #1复制

67

说明/提示

NOIP 2000 提高组第四题

见代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10][10];
int f[10][10][10][10];
int x,y,s;
int main() {
    //freopen("~~~.in","r",stdin);
    //freopen("~~~.out","w",stdout);
    cin>>n;
    while(cin>>x>>y>>s&&x&&y) {
        a[x][y]=s;
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int k=1; k<=n; k++) {
                for(int l=1; l<=n; l++) {
                    f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
                    if(i==k&&l==j)f[i][j][k][l]-=a[i][j];
                }
            }
        }
    }
    cout<<f[n][n][n][n];
    //exit(1);
    return 0;
}

相关文章:

P1004 [NOIP2000 提高组] 方格取数

题目描述 设有 &#xfffd;&#xfffd;NN 的方格图 (&#xfffd;≤9)(N≤9)&#xff0c;我们将其中的某些方格中填入正整数&#xff0c;而其他的方格中则放入数字 00。如下图所示&#xff08;见样例&#xff09;: 0 0 0 0 0 0 0 0 0 0 13 0 0 6 0 0 0 0 0…...

Leetcode.1024 视频拼接

题目链接 Leetcode.1024 视频拼接 Rating &#xff1a; 1746 题目描述 你将会获得一系列视频片段&#xff0c;这些片段来自于一项持续时长为 time秒的体育赛事。这些片段可能有所重叠&#xff0c;也可能长度不一。 使用数组 clips描述所有的视频片段&#xff0c;其中 clips[i…...

20个华为路由器常用的Python脚本,网工写自动化脚本时候可以参考!

你好&#xff0c;这里是网络技术联盟站。 昨天给大家介绍了10个华为交换机的Python脚本&#xff1a; 10个华为华为交换机常用的Python脚本&#xff0c;网络工程师收藏&#xff01; 大家反响不错&#xff0c;后期我会陆续出一下思科、H3C、锐捷等厂商的脚本&#xff0c;前期会…...

【kubernetes云原生】k8s资源管理命令与Namespace使用详解

目录 一、前言 二、k8s概述 三、k8s常用操作管理命令 3.1 kubectl 命令用法 3.2 常用控制台管理命令演示 3.2.1 获取全部节点信息 3.2.2 获取当前集群下全部pod 3.2.3 查看某个pod信息 3.2.4 获取当前集群下的所有namespace信息 3.2.5 查看当前集群下已创建的资源 3…...

String源码深度刨析

前言 我们将从源码角度深度分析特点&#xff0c;来提升对他们的了解以及设计。 String、StringBuilder、StringBuffer的常见面试题及四大区别可以参考&#xff1a;String、StringBuilder、StringBuffer的四大区别解析 String public final class Stringimplements java.io.Se…...

FreeRTOS - 消息队列

一.消息队列的概念及应用消息队列&#xff08;queue&#xff09;&#xff1a;可以在任务与任务间、中断和任务间传递消息&#xff0c;实现任务接收来自其他任务或中断的不固定的消息1.1任务需求1、使用消息队列检测串口输入2、通过串口发送字符串openled1&#xff0c;openled2&…...

怎样正确做 Web 应用的压力测试?

环境 首先环境是非常重要的&#xff0c;需要尽可能跟生产环境靠近。 比方说&#xff0c;使用同样的nginx版本&#xff0c;php的话需要启用fpm&#xff0c;zend-optimizer等等&#xff0c;参数配置也最好跟生产环境保持一致。 当然&#xff0c;php的版本更加需要保持一致&#x…...

php mysql大学生求职招聘资源信息网zkfdzkf67a8

1&#xff0e;系统登录&#xff1a;系统登录是用户访问系统的路口&#xff0c;设计了系统登录界面&#xff0c;包括用户名、密码和验证码&#xff0c;然后对登录进来的用户判断身份信息&#xff0c;判断是管理员用户还是普通用户。 2&#xff0e;系统用户管理&#xff1a;不管是…...

2023上海市“星光计划”职业院校技能大赛 网络安全竞赛试题任务书

2023上海市“星光计划”职业院校技能大赛 网络安全竞赛试题任务书 A模块基础设施设置/安全加固&#xff08;200分&#xff09; 一、项目和任务描述&#xff1a; 假定你是某企业的网络安全工程师&#xff0c;对于企业的服务器系统&#xff0c;根据任务要求确保各服务正常运行&…...

Spring事务源码:创建代理类

参考文章&#xff1a; 《Spring事务源码解析之tx:annotation-driven标签解析》 《Spring 源码解析—事务执行》 参考资料&#xff1a; 《Spring AOP源码&#xff1a;开启注解读取》 《Spring AOP源码2&#xff1a;查找增强器》 《Spring AOP源码3&#xff1a;实现代理》 …...

java14 使用增强的模式匹配切换表达式

野旷天低树&#xff0c;江清月近人。——唐代杜甫《月夜忆舍弟》 使用增强的模式匹配切换表达式(Switch Expressions with Enhanced Pattern Matching) Java 14中引入的“Switch Expressions with Enhanced Pattern Matching”这个功能。 这个功能可以让我们在使用switch cas…...

python【正则表达式】

正则表达式 1.正则的作用 正则表达式式一种可以让复杂的字符串变得简单的工具。 写正则表达式的时候就是用正则符号来描述字符串规则。 2.正则语法 需要导入模块 from re import fullmatch, findall, search2.1.第一类&#xff1a;匹配类符号 1&#xff09;普通字符—在…...

Ubuntu常见系统问题解决方式

Ubuntu常见系统问题解决方式Ubuntu每次开机后提示检测到系统程序出现问题的解决方法Ubuntu循环登陆问题问题描述原因解决方法文件夹打开缓慢Ubuntu启动后GUI界面卡住不动Ubuntu18.04使用过程中常遇到的问题Ubuntu每次开机后提示检测到系统程序出现问题的解决方法 首先&#xf…...

C/C++中的虚拟内存

文章目录一、虚拟内存二、C中的虚拟内存分配模型三、C中的虚拟内存分配模型四、堆区和栈区的区别一、虚拟内存 虚拟内存是一种实现在计算机软硬件之间的内存管理技术&#xff0c;它将程序使用到的内存地址&#xff08;虚拟地址&#xff09;映射到计算机内存中的物理地址&#…...

Qt C++与Python混合编程:补充错误

在提示中&#xff0c;需要引用Python.h&#xff0c;出现错误。 1、找不到Python.h 如果是pro工程&#xff0c;需要在里面配置&#xff1b; INCLUDEPATH /Users/xinnianwang/opt/anaconda3/include LIBS /Users/xinnianwang/opt/anaconda3/lib 如果是CMakeLists.txt需要配…...

2023-04-01:当Go语言遇见FFmpeg视频解码器,使用Go语言改写decode_video.c文件,提升视频解码效率与开发体验。

2023-04-01&#xff1a;当Go语言遇见FFmpeg视频解码器&#xff0c;使用Go语言改写decode_video.c文件&#xff0c;提升视频解码效率与开发体验。 答案2023-04-01&#xff1a; 步骤如下&#xff1a; 1.导入必要的依赖库&#xff0c;包括 fmt、os、unsafe 和其它 FFmpeg 库相关…...

Solidity 学习笔记

主要参考网上资料学习&#xff0c;个人学习笔记有删改&#xff0c;参考出处在文末列出。 0 基础 IDE: remixType Bool: bool public _bool true; 默认false;整型&#xff1a;int、uint、uint256&#xff0c;默认0;地址类型&#xff1a;address&#xff0c;分为 payable 和普…...

ThreadLocal原理

关键点总结&#xff1a; ThreadLocal更像是对其他类型变量的一层包装&#xff0c;通过ThreadLocal的包装使得该变量可以在线程之间隔离和当前线程全局共享。在Thread中有一个threadLocals变量&#xff0c;类型为ThreadLocal.ThreadLocalMap&#xff0c;ThreadLocalMap中key是Th…...

串操作指令详解 MOVS,LODS,STOS,CMPS,SCAS,REP

指令包括&#xff1a;MOVS&#xff0c;LODS&#xff0c;STOS&#xff0c;CMPS&#xff0c;SCAS&#xff0c;REP 串的概念&#xff1a;串是连续存放再内存中的字节块或字块。每个串有一个起始地址和长度&#xff0c; 待操作的数据串称为源串&#xff0c;目的地址称为目标串 目录…...

Java实现判断素数

1 问题 判断101-200之间有多少个素数&#xff0c;并输出所有素数。 2 方法 package homework04; public class Test05 { public static void main(String[] args) { for (int i 101; i < 201; i) { boolean flag true; for (int j 2; j…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

redis和redission的区别

Redis 和 Redisson 是两个密切相关但又本质不同的技术&#xff0c;它们扮演着完全不同的角色&#xff1a; Redis: 内存数据库/数据结构存储 本质&#xff1a; 它是一个开源的、高性能的、基于内存的 键值存储数据库。它也可以将数据持久化到磁盘。 核心功能&#xff1a; 提供丰…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...