奔两个冬天的搭配# Fashion - 美丽时尚
c*l
1 楼
【 以下文字转载自 Programming 讨论区 】
发信人: coupondeal (Coupon Deal), 信区: Programming
标 题: 求问一道动态规划的题目
发信站: BBS 未名空间站 (Mon Apr 28 13:16:18 2014, 美东)
Google code jam上的算法题：
我目前能想到的算法是O(k * 2^n * 2^n)
也就是说，求出所有组合在k=1, k=2, k=3....直到k=k时的最小正方形覆盖
但这个复杂度实在太大了，有没有更简便的算法？
Problem
You are given n points in the plane. You are asked to cover these points
with k squares.
The squares must all be the same size, and their edges must all be parallel
to the coordinate axes.
A point is covered by a square if it lies inside the square, or on an edge
of the square.
Squares can overlap.
Find the minimum length for the squares' edges such that you can cover the n
points with k squares.
Input
The first line of input gives the number of cases, N. N test cases follow.
The first line of each test contains two positive integers n and k. Each of
the next n lines contains a point as two integers separated by exactly one
space. No point will occur more than once within a test case.
Output
For each test case, you should output one line containing "Case #X: Y" (
quotes for clarity), where X is the number of the test case, starting from 1
, and Y is the minimum length for the squares' edges for that test case.
Limits
The points' coordinates are non-negative integers smaller than 64000.
1 ≤ N ≤ 10
Small dataset
1 ≤ k < n ≤ 7
Large dataset
1 ≤ k < n ≤ 15
Sample
Input
2
5 2
1 1
2 2
3 3
6 6
7 8
3 2
3 3
3 6
6 9
Output
Case #1: 2
Case #2: 3
发信人: coupondeal (Coupon Deal), 信区: Programming
标 题: 求问一道动态规划的题目
发信站: BBS 未名空间站 (Mon Apr 28 13:16:18 2014, 美东)
Google code jam上的算法题：
我目前能想到的算法是O(k * 2^n * 2^n)
也就是说，求出所有组合在k=1, k=2, k=3....直到k=k时的最小正方形覆盖
但这个复杂度实在太大了，有没有更简便的算法？
Problem
You are given n points in the plane. You are asked to cover these points
with k squares.
The squares must all be the same size, and their edges must all be parallel
to the coordinate axes.
A point is covered by a square if it lies inside the square, or on an edge
of the square.
Squares can overlap.
Find the minimum length for the squares' edges such that you can cover the n
points with k squares.
Input
The first line of input gives the number of cases, N. N test cases follow.
The first line of each test contains two positive integers n and k. Each of
the next n lines contains a point as two integers separated by exactly one
space. No point will occur more than once within a test case.
Output
For each test case, you should output one line containing "Case #X: Y" (
quotes for clarity), where X is the number of the test case, starting from 1
, and Y is the minimum length for the squares' edges for that test case.
Limits
The points' coordinates are non-negative integers smaller than 64000.
1 ≤ N ≤ 10
Small dataset
1 ≤ k < n ≤ 7
Large dataset
1 ≤ k < n ≤ 15
Sample
Input
2
5 2
1 1
2 2
3 3
6 6
7 8
3 2
3 3
3 6
6 9
Output
Case #1: 2
Case #2: 3
