当前位置: 首页 > 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…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...