首页 > 试题广场 >

carpet

[编程题]carpet

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

White Cloud has a rectangle carpet of $n*m$ . $Grid (i,j)$ has a color $colorA[i][j]$ and a cost $costA[i][j]$ .
White Rabbit will choose a subrectangle $B$ of $p*q$ from $A$ and the color of each grid is $colorB[0...p-1][0...q-1]$ , the cost of $B$ is the (maximum number in the corresponding subrectangle of $costA*(p+1)*(q+1)$ ).
Then $colorB$ is continuously translated and copied in an infinite times, that is, expand $colorB$ into an infinite new matrix, $colorC$ , which satisfies $colorC[i][j]=colorB[i mod p][j mod q]$ .
White Rabbit must ensure that $colorA$ is a subrectangle of $colorC$ .
You need to find the minimum cost way.

输入描述:

The first line of input contains two integers 
For the next line of  lines, each line contains  lowercase English characters, denoting .
For the next line of  lines, each line contains  integers in range [0,1000000000], denoting .

输出描述:

Print the minimum cost.

示例1

输入

2 5
acaca
acaca
3 9 2 8 7
4 5 7 3 1

输出

说明

choose subrectangle colorA[1...1][3...4]=ca, After copying unlimited copies
colorC=
cacacacaca ...
cacacacaca ...
cacacacaca ...
cacacacaca ...
cacacacaca ...
.........
colorA is a subrectangle of colorC
the cost is max(3,1)*(1+1)*(2+1).

算法知识视频讲解

Cur1ed

发表于 2020-07-29 09:04:46

题意有一个n*m的地毯，aij表示地毯每格的元素，bij表示地毯每格的价格，要求选取一块价格最大值最小的地毯，并且这块地毯无限铺开之后，原地毯是其子矩阵。题解先找到这个矩阵的最小循环节子矩阵，求一下每行的循环节长度用map记录，取出现次数为m并且循环节长度最小的；每列也求一下展开全文

andif

发表于 2023-06-23 02:31:33

题意让你求一个子矩阵，这个子矩阵无限拓展之后，可以让原来的矩阵变成这个无限矩阵的子矩阵，并且要使得cost最小， cost是这个子矩阵的最大值 * (子矩阵宽 + 1) * (子矩阵高 + 1) 思路很显然，我们要求的矩阵尽量小，因为横向和纵向不相互影响，那么我们可以横向纵向求最小周期，这样就展开全文

问题信息

kmp与扩展kmp

难度：

0条回答 0收藏 1浏览

通过挑战的用户

查看代码

蚂蚁金服-智能...

2018-08-31 14:29:13
forever...

2018-08-10 16:49:48
牛客1941791号

2018-08-07 20:36:35
hypoxia

2018-08-03 16:47:14
SUSTC_1...

2018-08-01 10:57:33

carpet

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题