100290. 使矩阵满足条件的最少操作次数

server/2024/10/21 11:37:22/

https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/
正难则反。
暴力的遍历每一修改的情况,0-9;根据前一列的状态进行转移过来,
下面是状态转移方程
f ( i , j ) = m a x ( f ( i , j ) , f ( i + 1 , k ) + c n t ( i , k ) ) k ! = j ; f(i, j) = max(f(i, j),f(i+1, k)+cnt(i, k)) k!=j; f(i,j)=max(f(i,j),f(i+1,k)+cnt(i,k))k!=j;
c n t ( i , j ) :第 i 列值为 j 的个数; cnt(i, j):第i列值为j的个数; cnt(i,j):第i列值为j的个数;
最后直接 n ∗ m − m a x ( f [ 0 ] ) n*m-max(f[0]) nmmax(f[0])

class Solution {
public:int minimumOperations(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();vector<vector<int>> cnt(n, vector<int>(10,0));for(int i=0;i<m;i++){for(int j=0;j<n;j++){cnt[j][grid[i][j]]++;}}vector<vector<int>> dp(n, vector<int>(10, 0));for(int i=n-1;i>=0;i--){for(int j=0;j<10;j++){if(i == n-1){dp[i][j] = cnt[i][j];}else{for(int k = 0;k<10;k++){if(k == j) continue;dp[i][j] = max(dp[i][j],dp[i+1][k]+cnt[i][j]); }}}}return n*m-*max_element(dp[0].begin(), dp[0].end());}
};

http://www.ppmy.cn/server/19909.html

相关文章

《HCIP-openEuler实验指导手册》1.7 Apache虚拟主机配置

知识点 配置步骤 需求 域名访问目录test1.com/home/source/test1test2.com/home/source/test2test3.com/home/source/test3 创建配置文件 touch /etc/httpd/conf.d/vhost.conf vim /etc/httpd/conf.d/vhost.conf文件内容如下 <VirtualHost *.81> ServerName test1.c…

浅谈叉车车载电脑的市场现状

叉车的起源 叉车源于美国&#xff0c;兴于日本&#xff0c;虽然中国起步较晚&#xff0c;但是近些年来发展迅速。叉车又称叉式装载车&#xff0c;是对于成件托盘类货物进行装卸、堆垛和短距离运输&#xff0c;实现重物搬运作业的轮式工业车辆。 叉车的分类 叉车分为以上六大类…

【1569】jsp学生学籍管理系统Myeclipse开发sqlserver数据库web结构jsp编程计算机网页项目

一、源码特点 jsp 学生学籍管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为sqlserver2…

【静态分析】静态分析笔记09 - 污点分析

参考&#xff1a; 【课程笔记】南大软件分析课程—16课时完整版 - 知乎 ------------------------------------------------------------------------------- 1. 信息流安全 访问控制&#xff1a;关注信息访问。 信息流安全&#xff1a;关注信息传播。 信息流&#xff1a…

2024蓝桥杯CTF--逆向

蓝桥杯付费CT--逆向 题目&#xff1a;RC4题目&#xff1a;happytime总结&#xff1a; 题目&#xff1a;RC4 先查壳&#xff0c;无壳&#xff0c;并且是32位&#xff1a; 用32位的ida打开&#xff0c;直接定位到main函数&#xff1a; 重点关注sub_401005函数&#xff0c;这个应…

Linux计划任务书以及定时任务的编写

一、程序可以通过两种方式执行&#xff1a; 手动执行利用调度任务&#xff0c;依据一定的条件自动执行 自动执行可通过一下两个命令来实现: &#xff08;1&#xff09;At &#xff08;单一工作调度&#xff09; &#xff08;2&#xff09;Cron &#xff08;循环工作调度&a…

JavaScript基础——1.js基础语法

js全称JavaScript,是一种轻量级的面向对象的编程语言,既能用在浏览器中控制页面交互,也能用在服务器端作为网站后台(借助 Node.js),因此 JavaScript 是一种全栈式的编程语言。 JavaScript 与 HTML 和 CSS 共同构成了我们所看到的网页,其中: HTML 用来定义网页的内容,…

深入理解操作系统与计算机体系结构

文章目录 操作系统(Operator System)为什么要有操作系统操作系统是如何进行管理的为什么说操作系统是安全&#xff0c;稳定&#xff0c;高效的理解系统调用和库函数 操作系统(Operator System) 概念&#xff1a; 操作系统&#xff08;Operating System&#xff0c;简称OS&…