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

[NOIP2014普及组]子矩阵

题目:洛谷P2258、Vijos P1914、codevs 3904。

题目大意:给你一个矩阵,要你找一个r行c列的子矩阵,求最小分值(子矩阵和分值的定义见原题)。

解题思路:n和m比较小,考虑暴力。

发现时间复杂度为$O(C_n^r ×C_m^c)$,可能会炸掉。因此考虑优化。

我们可以只暴力出行,然后通过dp求出和:

设f[i][j]表示选i列最后一个选j所得到的最小分值,x[i][j]表示第i列和第j列能产生的分值(不包括上下),y[i]表示第i列能产生出的分值(上下),这些都表示当前暴力到的状态。

则$f[i][j]=f[i-1][k]+y[j]+x[k][j](2\leq i\leq c,i\leq j\leq m,i-1\leq k\leq j-1)$,边界f[1][i]=y[i]。

最后答案为$min(f[c][i])(c\leq i\leq m)$。

dp时间复杂度是$O(m^3)$的,那么总时间复杂度优化到$O(C_n^r × m^3)$。

C++ Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define For(i,a,b) for(register int i=a;i<=b;++i)
#define min(a,b) (((a)<(b))?(a):(b))
int a[17][17],n,m,r,c,num[17],ans,f[17][17],y[17],x[17][17];
void dp(){
	memset(f,0x3f,sizeof f);
	memset(f[1],0,sizeof f[1]);
	memset(y,0,sizeof y);
	memset(x,0,sizeof x);
	For(i,1,m)For(j,2,r)
	y[i]+=abs(a[num[j]][i]-a[num[j-1]][i]);
	For(i,1,m)
	For(j,i+1,m)
	For(k,1,r)
	x[i][j]+=abs(a[num[k]][i]-a[num[k]][j]);
	memcpy(f[1],y,sizeof f[1]);
	For(i,2,c)
	For(j,i,m)
	For(k,i-1,j-1)
	f[i][j]=min(f[i][j],f[i-1][k]+y[j]+x[k][j]);
	For(i,c,m)ans=min(ans,f[c][i]);
}
void dfs(int now){
	if(now>r){
		dp();
		return;
	}
	For(i,num[now-1]+1,n){
		num[now]=i;
		dfs(now+1);
	}
}
int main(){
	ans=0x3f3f3f3f;
	scanf("%d%d%d%d",&n,&m,&r,&c);
	For(i,1,n)For(j,1,m)
	scanf("%d",&a[i][j]);
	num[0]=0;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}

 

转载于:https://www.cnblogs.com/Mrsrz/p/7694233.html

相关文章:

  • python中的数据结构
  • 结对编程——四则运算界面化
  • [No000010F]Git8/9-使用GitHub
  • 微信
  • Android连接热点的Socket文件传输
  • JS中的函数知识点
  • 上传第三方jar包至maven私服,以geotools为例
  • Shell记录-Shell命令(find)
  • 上海公积金社保业务办理
  • Ubuntu 16.04下解决sublime text3无法输中文问题
  • week5
  • lua实现table转string
  • 毕业设计10-26星期四
  • 洛谷P3469 [POI2008]BLO-Blockade
  • 使用MEMCACHED实现缓存
  • ABAP的include关键字,Java的import, C的include和C4C ABSL 的import比较
  • Angular 响应式表单 基础例子
  • Angularjs之国际化
  • gf框架之分页模块(五) - 自定义分页
  • Git学习与使用心得(1)—— 初始化
  • hadoop入门学习教程--DKHadoop完整安装步骤
  • JavaScript 事件——“事件类型”中“HTML5事件”的注意要点
  • JavaScript对象详解
  • k8s 面向应用开发者的基础命令
  • MyEclipse 8.0 GA 搭建 Struts2 + Spring2 + Hibernate3 (测试)
  • MySQL的数据类型
  • PHP变量
  • Python中eval与exec的使用及区别
  • ucore操作系统实验笔记 - 重新理解中断
  • 分布式任务队列Celery
  • 基于Vue2全家桶的移动端AppDEMO实现
  • 技术发展面试
  • 排序算法学习笔记
  • 三分钟教你同步 Visual Studio Code 设置
  • 使用权重正则化较少模型过拟合
  • 适配iPhoneX、iPhoneXs、iPhoneXs Max、iPhoneXr 屏幕尺寸及安全区域
  • 《码出高效》学习笔记与书中错误记录
  • scrapy中间件源码分析及常用中间件大全
  • 阿里云IoT边缘计算助力企业零改造实现远程运维 ...
  • 通过调用文摘列表API获取文摘
  • ​批处理文件中的errorlevel用法
  • #DBA杂记1
  • #QT(智能家居界面-界面切换)
  • $(selector).each()和$.each()的区别
  • (1)SpringCloud 整合Python
  • (板子)A* astar算法,AcWing第k短路+八数码 带注释
  • (附源码)ssm考试题库管理系统 毕业设计 069043
  • (四)Linux Shell编程——输入输出重定向
  • (原創) 人會胖會瘦,都是自我要求的結果 (日記)
  • (转) ns2/nam与nam实现相关的文件
  • ... fatal error LINK1120:1个无法解析的外部命令 的解决办法
  • .NET Core 网络数据采集 -- 使用AngleSharp做html解析
  • .NET Core 项目指定SDK版本
  • .net解析传过来的xml_DOM4J解析XML文件
  • @我的前任是个极品 微博分析