g*******s
发帖数: 2963 | 1 第一轮电面问道的。
一个大的2D rectangle， size是M*N.
每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。 |
q****x
发帖数: 7404 | 2 什么是挖到不能挖？
【在 g*******s 的大作中提到】
: 第一轮电面问道的。
: 一个大的2D rectangle， size是M*N.
: 每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
: 问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。
|
n******e
发帖数: 957 | 3 你的意思是m和n也是给定的，然后输出一个方法让挖完以后的剩余最小是吧？ |
g*******s
发帖数: 2963 | 4 就是在剩余的空间里找不到一个满足 m×n的rectangle了。 剩余面积>=m*n是必要条件
，但不是充分条件。 有可能剩余不规则面积>>m*n,但并不能找出一块m×n的rectangle
了。
【在 q****x 的大作中提到】
: 什么是挖到不能挖？
|
g*******s
发帖数: 2963 | 5 这个问题我在想能不能倒过来想？
就好像有一个M*N的空间，每次给你一块m*n的板子去填补这个空间，要求最后尽量空间
被填满而没有洞。 所以问题就是每次你怎么根据给你的m*n去把板子填到最合适的地方。
感觉像个DP的问题。。。。。。 |
n******e
发帖数: 957 | |
G****A
发帖数: 4160 | 7 题目没说清楚啊。
你的意思是不是？
const int m = xxx;
const int n = xxx;
【在 g*******s 的大作中提到】
: 第一轮电面问道的。
: 一个大的2D rectangle， size是M*N.
: 每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
: 问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。
|
z*******g
发帖数: 18 | 8 我觉得这题可以用dp解决，
建一个2*2的矩阵，int A[M][N]
A[x][y]表示大小 x*y 的rectangle挖完后剩下的面积。
然后赋值好初始值后，用下面这个关系来做iterate，
A[x][y] = min( min(A[x-m][y]+A[m][y-n], A[x-m][n]+A[x][y-n]),
min(A[x-n][y]+A[n][y-m], A[x-n][m]+A[x][y-m])
)
如果x-m小于0的话就扔掉这项，同样的对于其他的小于0的项。
第一项和第二项就是把小的rectangle转个90度放一下。
不知道这方法可行不？望牛人多指点。
【在 g*******s 的大作中提到】
: 第一轮电面问道的。
: 一个大的2D rectangle， size是M*N.
: 每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
: 问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。
|
g*******s
发帖数: 2963 | 9 m和n是不定的，每次可以变。关键就是每次怎么根据这个动态的size选择放到哪里
【在 G****A 的大作中提到】
: 题目没说清楚啊。
: 你的意思是不是？
: const int m = xxx;
: const int n = xxx;
|
f**********e
发帖数: 288 | |
n******e
发帖数: 957 | 11 你这个表述的太不清楚了，输入输出，变量定量，关系是什么都不清楚，叫人怎么看？
【在 g*******s 的大作中提到】
: m和n是不定的，每次可以变。关键就是每次怎么根据这个动态的size选择放到哪里
|
b*******n
发帖数: 46 | |
