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

Problem E. 矩阵游戏 (2023年ccpc河南省赛)

原题链接:
https://codeforces.com/gym/104354

题意:

有一个n*m的矩阵,只有三种字符:0,1和?。从[1,1]走到[n,m],每次只能向下走或者向下走。当走到1的时候得一分,走到0的时候不得分,走到?的时候可以将他变为1从而得到一分,或者不变,求所有从[1,1]走到[n,m]的路径的得分的最大值

思路:

f[i][j][k]表示走到[i,j]恰好有k个?变成1的方案数的最大得分
状态转移:
a[i][j]‘0’:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])
a[i][j]
‘1’:f[i][j][k]=max(f[i-1][j][k]+1,f[i][j-1][k]+1)
a[i][j]==‘?’:
改:f[i][j][k]=max(f[i-1][j][k-1]+1,f[i][j-1][k-1]+1)
不改:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])

那么这样的空间复杂度是n* m * x,会mle

于是考虑将数组优化到二维:f[j][k]

1.将k从大到小枚举
在转移的时候,如果按正常枚举,就会出现重复的情况,这时候只需要将k从大到小进行枚举,就避免了重复

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
int f[505][1005];
char a[505][505];
bool  cheek(int x,int y){if(x>=1&&x<=n&&y>=1&&y<=m) return true;else return false;
}
void sove(){scanf("%d%d%d",&n,&m,&x);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int j=0;j<=m;j++){for(int k=0;k<=x;k++){f[j][k]=-0x3f3f3f3f;}}if(a[1][1]=='1'){f[1][0]=1;}else if(a[1][1]=='0'){f[1][0]=0;}else{f[1][1]=1;f[1][0]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=x;k>=0;k--){if(a[i][j]=='1'){if(cheek(i-1,j)){f[j][k]=max(f[j][k],f[j][k]+1);}if(cheek(i,j-1)){f[j][k]=max(f[j][k],f[j-1][k]+1);}}else if(a[i][j]=='0'){if(cheek(i,j-1)){f[j][k]=max(f[j][k],f[j-1][k]);}				}else{if(cheek(i-1,j)){if(k-1>=0) f[j][k]=max(f[j][k],f[j][k-1]+1);}if(cheek(i,j-1)){f[j][k]=max(f[j-1][k],f[j][k]);if(k-1>=0)f[j][k]=max(f[j][k],f[j-1][k-1]+1);}		}}}}int ans=0;for(int i=0;i<=x;i++){ans=max(ans,f[m][i]);}cout<<ans<<endl;
}
int main(){int t;scanf("%d",&t);while(t--){sove();}return 0;
}

2.滚动数组
在转移的时候只用到了i和i-1层,那么我们就将i这一维开两个,在转移的时候在两维之间相互转移就可以了

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
int f[3][505][1005];
char a[505][505];
bool  cheek(int x,int y){if(x>=1&&x<=n&&y>=1&&y<=m) return true;else return false;
}
void sove(){scanf("%d%d%d",&n,&m,&x);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=0;i<3;i++){for(int j=0;j<=m;j++){for(int k=0;k<=x;k++){f[i][j][k]=-0x3f3f3f3f;}}
}if(a[1][1]=='1'){f[1][1][0]=1;}else if(a[1][1]=='0'){f[1][1][0]=0;}else{f[1][1][1]=1;f[1][1][0]=0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=0;k<=x;k++){if(a[i][j]=='1'){if(cheek(i-1,j)){f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k]+1);}if(cheek(i,j-1)){f[i&1][j][k]=max(f[i&1][j][k],f[i&1][j-1][k]+1);}}else if(a[i][j]=='0'){if(cheek(i-1,j)){f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k]);}if(cheek(i,j-1)){f[i&1][j][k]=max(f[i&1][j][k],f[i&1][j-1][k]);}				}else{if(cheek(i-1,j)){f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k]);if(k-1>=0)f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k-1]+1);}if(cheek(i,j-1)){f[i&1][j][k]=max(f[i&1][j][k],f[i&1][j-1][k]);if(k-1>=0)f[i&1][j][k]=max(f[i&1][j][k],f[i&1][j-1][k-1]+1);}	}}}}int ans=0;for(int i=0;i<=x;i++){ans=max(ans,f[n&1][m][i]);}	cout<<ans<<endl;
}
int main(){int t;scanf("%d",&t);while(t--){sove();}return 0;
}

相关文章:

Problem E. 矩阵游戏 (2023年ccpc河南省赛)

原题链接&#xff1a; https://codeforces.com/gym/104354 题意&#xff1a; 有一个n*m的矩阵&#xff0c;只有三种字符&#xff1a;0,1和?。从[1,1]走到[n,m],每次只能向下走或者向下走。当走到1的时候得一分&#xff0c;走到0的时候不得分&#xff0c;走到?的时候可以将他…...

数字孪生模型构建理论及应用

源自&#xff1a;计算机集成制造系统 作者&#xff1a;陶飞 张贺 戚庆林 徐 俊 孙铮 胡天亮 刘晓军 刘庭煜 关俊涛 陈畅宇 孟凡伟 张辰源 李志远 魏永利 朱铭浩 肖斌 摘 要 数字孪生作为实现数字化转型和促进智能化升级的重要使能途径&#xff0c;一直备受各…...

Vue面试题:30道含答案和代码示例的练习题

Vue中的双向数据绑定是怎么实现的&#xff1f; 双向数据绑定通过使用v-model指令实现。v-model指令会在表单元素上创建一个监听器&#xff0c;在用户输入时实时更新Vue实例的数据&#xff0c;并且在Vue实例数据变化时更新表单元素的值。 如何在Vue中定义一个方法&#xff1f;…...

2023-05-09 LeetCode每日一题(有效时间的数目)

2023-05-09每日一题 一、题目编号 2437. 有效时间的数目二、题目链接 点击跳转到题目位置 三、题目描述 给你一个长度为 5 的字符串 time &#xff0c;表示一个电子时钟当前的时间&#xff0c;格式为 “hh:mm” 。最早 可能的时间是 “00:00” &#xff0c;最晚 可能的时间…...

第三节课 Linux文件权限

目录 文件属性详解 权限修改 文件所有者与属组修改 文件默认权限修改 Linux是多人多任务的操作系统&#xff0c;因此可能常常会有多人使用一台机器&#xff0c; 为了考虑每个人的隐私、方便用户合作&#xff0c;每个文件都有三类用户&#xff0c;权限是基于这三类用户设定的…...

开发STC89C51系列单片机需要的单片机技术

端口操作&#xff1a;控制单片机的输入输出端口&#xff0c;与外界进行通信。中断优先级&#xff1a;当多个中断同时发生时&#xff0c;确定哪个中断优先级更高&#xff0c;优先响应。时钟模块&#xff1a;控制单片机的时钟&#xff0c;可以精确计时。PWM技术&#xff1a;实现模…...

分布式键值存储是什么?(分布式键值存储大值)

文章目录 什么是分布式键值存储&#xff1f;分布式键值存储“大值”指什么&#xff1f; 什么是分布式键值存储&#xff1f; 分布式键值存储是一种分布式数据存储系统&#xff0c;它将数据存储为键值对的形式&#xff0c;并将这些键值对分散在多个节点上。每个节点都可以独立地…...

多线程(线程同步和互斥+线程安全+条件变量)

线程互斥 线程互斥&#xff1a; 任何时刻&#xff0c;保证只有一个执行流进入临界区访问临界资源&#xff0c;通常对临界资源起到保护作用 相关概念 临界资源&#xff1a; 一次仅允许一个进程使用的共享资源临界区&#xff1a; 每个线程内部&#xff0c;访问临界资源的代码&am…...

Flutter学习——开发Flutter需要的技能

第二章 Flutter开发所需要掌握的知识 文章目录 第二章 Flutter开发所需要掌握的知识前言一、开发语言Dart语言Android/Ios知识 二、组件学习三、调试与性能优化总结 前言 上一章&#xff0c;介绍了Flutter的来源和平台支持及特点&#xff0c;这一章&#xff0c;来梳理一下学习…...

SPSS如何进行因子分析和主成分分析之案例实训?

文章目录 0.引言1.因子分析2.主成分分析 0.引言 因科研等多场景需要进行数据统计分析&#xff0c;笔者对SPSS进行了学习&#xff0c;本文通过《SPSS统计分析从入门到精通》及其配套素材结合网上相关资料进行学习笔记总结&#xff0c;本文对因子分析和主成分分析进行阐述。 1.因…...

图标字体与HTML转义字符:网页设计中的两个关键概念

在网页设计中&#xff0c;图标字体和HTML转义字符是两个重要的概念。图标字体用于显示网页的图标&#xff0c;可以让用户更加直观地理解网页的内容。而HTML转义字符则用于在网页中插入特殊的字符&#xff0c;以保证网页的安全性和可读性。 一、图标字体 在网页中显示图标&#…...

Elasticsearch详解

文章目录 概览使用与ES交互索引创建索引查询索引删除文档创建修改文档局部修改文档查询文档删除全查询 整合SpringBootpom依赖application.ymlElasticsearchAutoConfigurationElasticsearchPropertiesElasticsearchConstantPersonSearchPageHelperPersonServiceBaseElasticsear…...

学习笔记(13)网络基础

目录 1&#xff0c;get与post的区别2&#xff0c;JSON解析2.1&#xff0c;JSON.stringify2.2&#xff0c;JSON.parse 3&#xff0c;cookie3.1&#xff0c;set方法3.2&#xff0c;cookie方法用于设置响应头&#xff0c; 4&#xff0c;http模块4.1&#xff0c;请求报文和响应报文…...

LeertCode 134 加油站

题目&#xff1a; 在一条环路上有 n 个加油站&#xff0c;其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车&#xff0c;从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发&#xff0c;开始时油箱为空。给定两个整数数组 …...

python文件操作的基本流程

引入 程序运行过程中产生的数据会保存到内存中&#xff0c;如果想要永久保存下来&#xff0c;就必须将数据存放在硬盘上&#xff0c;应用程序如果想要操作计算机的硬件就必须通过操作系统&#xff0c;文件就是操作系统提供给应用程序来操作硬盘的虚拟概念&#xff0c;应用程序…...

1. 两数之和

原题链接&#xff1a; 1. 两数之和 https://leetcode.cn/problems/two-sum/ 完成情况&#xff1a; ##1. n 2 n^2 n2复杂度 2.HashMap进行优化 3.空间换时间方法 即&#xff0c;构建一个 1 0 − 9 10^-9 10−9 到 1 0 9 10^9 109这个大的数组&#xff0c;然后把数填进去&…...

操作系统:06 进程通信

1 基本概念 进程间通信是指两个或多个进程之间交互数据的过程&#xff0c;因为进程之间是相互独立的&#xff0c;为了协同工作必须进行进程间交互数据 2 进程间通信的分类 2.1 简单的进程间通信&#xff1a; 信号(携带附加数据)、文件、命令行参数、环境变量表 2.2 传统的进…...

WRF模式

随着生态文明建设和“碳中和”战略的持续推进&#xff0c;我国及全球气候变化及应对是政府、科学界及商业界关注的焦点。气候是多个领域&#xff08;生态、水资源、风资源及碳中和等问题&#xff09;的主要驱动因素&#xff0c;合理认知气候变化有利于解释生态环境变化机理及过…...

2直接连接的网络与VLAN划分【实验】【计算机网络】

2直接连接的网络与VLAN划分【实验】【计算机网络】 前言推荐2直接连接的网络与VLAN划分2.1共享式以太网和交换式以太网实验目的实验内容及实验环境实验原理共享式以太网交换式以太网 实验过程搭建实验环境初始化序训练操作共享式以太网-操作交换式以太网查看共享式以太网冲突查…...

【Linux0.11代码分析】04 之 head.s 启动流程

【Linux0.11代码分析】04 之 head.s 启动流程 一、boot/head.s 系列文章如下&#xff1a; 系列文章汇总&#xff1a;《【Linux0.11代码分析】之 系列文章链接汇总&#xff08;全&#xff09;》 . 1.《【Linux0.11代码分析】01 之 代码目录分析》 2.《【Linux0.11代码分析】02 之…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...