Land acquisition (USACO contest problem)
Разница между en1 и en2, 4 символ(ов) изменены
Problem 1: Land Acquisition [Paul Christiano, 2007]↵

Farmer John is considering buying more land for the farm and has↵
his eye on N (1 <= N <= 50,000) additional rectangular plots, each↵
with integer dimensions (1 <= width_i <= 1,000,000; 1 <= length_i↵
<= 1,000,000).↵

If FJ wants to buy a single piece of land, the cost is $1/square↵
unit, but savings are available for large purchases. He can buy↵
any number of plots of land for a price in dollars that is the width↵
of the widest plot times the length of the longest plot. Of course,↵
land plots cannot be rotated, i.e., if Farmer John buys a 3x5 plot↵
and a 5x3 plot in a group, he will pay 5x5=25.↵

FJ wants to grow his farm as much as possible and desires all the↵
plots of land. Being both clever and frugal, it dawns on him that↵
he can purchase the land in successive groups, cleverly minimizing↵
the total cost by grouping various plots that have advantageous↵
width or length values.↵

Given the number of plots for sale and the dimensions of each,↵
determine the minimum amount for which Farmer John can purchase all↵

PROBLEM NAME: acquire↵

INPUT FORMAT:↵

* Line 1: A single integer: N↵

* Lines 2..N+1: Line i+1 describes plot i with two space-separated↵
        integers: width_i and length_i↵

SAMPLE INPUT:↵

4↵
100 1↵
15 15↵
20 5↵
1 100↵

INPUT DETAILS:↵

There are four plots for sale with dimensions as shown.↵

OUTPUT FORMAT:↵

* Line 1: The minimum amount necessary to buy all the plots.↵

SAMPLE OUTPUT:↵

500↵

OUTPUT DETAILS:↵

The first group contains a 100x1 plot and costs 100. The next group↵
contains a 1x100 plot and costs 100. The last group contains both the 20x5↵
plot and the 15x15 plot and costs 300. The total cost is 500, which is↵
minimal.↵

------------------↵

my solution gives a O(n^2) algorithm, and it's not good since n<=
5*10^54. my solution sketch:↵

first we sort the pairs(from their width) consider 2 pairs the first with width w1 and length l1 and another with width w2 and l2,↵
if w1 <= w2 & l1 <= l2 then we can buy these two lands together without considering the first land and paying w2*l2 so we can simply discard these situations as below↵

after we sort the lands we change it so that their width would be increasing and their length would be decreasing(this can be easily done with a stack...), after that we can conclude that any form of buying the lands is decomposing the lands into sequences and paying every sequence,↵
for example if w1 < w2 < w3 < w4 and l1 > l2 > l3 > l4 one form of paying is joining 1 and 2 and then paying for 3 and then paying for 4, the sequnces are: [1..2] , [3..3] , [4..4] we can easily conclude if a form of buying is such that the lands joint, dont form a sequence by including the lands so that we can form a sequence results in decreasing the price,↵

now we can easily put a dp and update the dp with(O(n)) (how?) giving an algorithm of O(n^2),↵

the real dp algorithm should be less , plz help :)↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский shengdebao 2016-03-18 09:45:59 4 Tiny change: ' since n<=10^5. my solut' -> ' since n<=5*10^4. my solut'
en1 Английский shengdebao 2016-03-18 09:44:36 3014 Initial revision (published)