l*******p
发帖数: 7 | 1 there is a N X M array A, some of them are 1 and the others are zero.
Given an integer K, you have to find rectangles in this matrix whose side
length
is no bigger than K, such that the rectangles together cover the all
ones in the matrix, but to minimize the utility function U
the utility function U = number of rectangles used * 10 + sum of areas of
all rectangles.
rectangle in the matrix is 2D interval [i, j] X [ii, jj]
where j-i+1 and | O*******d
发帖数: 20343 | 2 你的问题和这个问题类似。
Strawberry Fields
Strawberries are growing in a rectangular field of length and width at most
50. You want to build greenhouses to enclose the strawberries. Greenhouses
are rectangular, axis-aligned with the field (i.e., not diagonal), and may
not overlap. The cost of each greenhouse is $10 plus $1 per unit of area
covered.
Write a program that chooses the best number of greenhouses to build, and
their locations, so as to enclose all the strawberries as cheaply as
possible. Heuristi | l*******p
发帖数: 7 | 3 简直就是一样啊
大虾有没有什么解法每
most
【在 O*******d 的大作中提到】
: 你的问题和这个问题类似。
: Strawberry Fields
: Strawberries are growing in a rectangular field of length and width at most
: 50. You want to build greenhouses to enclose the strawberries. Greenhouses
: are rectangular, axis-aligned with the field (i.e., not diagonal), and may
: not overlap. The cost of each greenhouse is $10 plus $1 per unit of area
: covered.
: Write a program that chooses the best number of greenhouses to build, and
: their locations, so as to enclose all the strawberries as cheaply as
: possible. Heuristi
| O*******d
发帖数: 20343 | 4 解这种问题比较费脑子。 我还没有时间来解。 根据题目中的说法，好像在有限时间内
不一定能找到最佳解。
【在 l*******p 的大作中提到】
: 简直就是一样啊
: 大虾有没有什么解法每
:
: most
| N*********y
发帖数: 105 | 5 怎么給我的感覺，最近這一類的問題在面試中突然多起來了？感覺回到小時候了，呵呵。
【在 O*******d 的大作中提到】
: 解这种问题比较费脑子。 我还没有时间来解。 根据题目中的说法，好像在有限时间内
: 不一定能找到最佳解。
| c*****t
发帖数: 1879 | 6 其实这题就是用个 tree + cache 。而 DP 的实质也就是某种 tree + cache 。
这道题稍微麻烦点，因为有 associativity 所以用 DP 麻烦了点。但是从
tree + cache，也就是在 brute force 上加 cache 入手就相对容易很多。
【在 O*******d 的大作中提到】
: 解这种问题比较费脑子。 我还没有时间来解。 根据题目中的说法，好像在有限时间内
: 不一定能找到最佳解。
|
|
