试着求一个Jcpenny的code - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PennySaver - 省钱一族

试着求一个Jcpenny的code

试着求一个Jcpenny的code# PennySaver - 省钱一族

g*s2010-04-22 07:04

1 楼

第一轮电面问道的。
一个大的2D rectangle， size是M*N.
每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。

V*x2010-04-22 07:04

2 楼

就是那种收据上的code，用来做他们家的收据做survey，可以打印15%胖子的，要求7天
以内的
包子求

q*x2010-04-22 07:04

3 楼

什么是挖到不能挖？

【在 g*******s 的大作中提到】

: 第一轮电面问道的。
: 一个大的2D rectangle， size是M*N.
: 每次从中挖去一块小的rectangle， size可以是任意m*n， m<=M, n<=N
: 问如何挖的算法最优，也就是挖到不能挖的时候，剩余的面积最小。

h*a2010-04-22 07:04

4 楼

前天网上有20%的jcpenny胖子来着。

n*e2010-04-22 07:04

5 楼

你的意思是m和n也是给定的，然后输出一个方法让挖完以后的剩余最小是吧？

y*a2010-04-22 07:04

6 楼

u don't need that. Just google it. there is free 15% code online. all the su
rvey get that code.
also, now t here is 10 off 10 deal

【在 V***x 的大作中提到】

: 就是那种收据上的code，用来做他们家的收据做survey，可以打印15%胖子的，要求7天
: 以内的
: 包子求

g*s2010-04-22 07:04

7 楼

就是在剩余的空间里找不到一个满足 m×n的rectangle了。剩余面积>=m*n是必要条件
，但不是充分条件。有可能剩余不规则面积>>m*n,但并不能找出一块m×n的rectangle
了。

【在 q****x 的大作中提到】

: 什么是挖到不能挖？

g*s2010-04-22 07:04

8 楼

这个问题我在想能不能倒过来想？
就好像有一个M*N的空间，每次给你一块m*n的板子去填补这个空间，要求最后尽量空间
被填满而没有洞。所以问题就是每次你怎么根据给你的m*n去把板子填到最合适的地方。
感觉像个DP的问题。。。。。。

n*e2010-04-22 07:04

9 楼

貌似不像dp

G*A2010-04-22 07:04

10 楼

题目没说清楚啊。
你的意思是不是？
const int m = xxx;
const int n = xxx;

【在 g*******s 的大作中提到】

z*g2010-04-22 07:04

11 楼

我觉得这题可以用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 的大作中提到】

g*s2010-04-22 07:04

12 楼

m和n是不定的，每次可以变。关键就是每次怎么根据这个动态的size选择放到哪里

【在 G****A 的大作中提到】

: 题目没说清楚啊。
: 你的意思是不是？
: const int m = xxx;
: const int n = xxx;