首页 > ACM题库 > HDU-杭电 > hdu 2559 Garbage collecting station待解决[解题报告]C++
2014
02-10

hdu 2559 Garbage collecting station待解决[解题报告]C++

Garbage collecting station

问题描述 :

As everyone knows, the garbage collecting station is very important to our daily life. With the growing of the city, more and more garbage need to be collected timely. First, let us see what will the garbage collecting station do everyday.
The station divide the city into N*M blocks, each block contains some buindings, as the picture below shows. And the garbage collecting station lies at the suburban district, but not inside any one of these blocks.


The station will sort the blocks (b1, b2, … bK, K = N*M )by their priority in a line. For instance, after the sort process, the blocks will be arranged as a sequence b1. b2. b3….bK, then the garbage collecting lorry will begin to collect garbage at b1, loading the garbage at b1, then go to b2, loading garbage then go to b3, and so on. After loaded the garbage at bK, the lorry will go to the station and upload all the garbage.

Now the station want to build another two stations, and these two stations will build inside two different blocks bi and bj (i<j). And the garbage of blocks b1 to bi will be carried to bi, the garbage of blocks bi+1 to bj will be carried to bj, the garbage of blocks bj+1 to bK will be carried to the station at the suburban district.

Now the problem is: we assume that carrying one unit of garbage in one meter will cost $1. Given the weight of the garbage of each block and the distance between bi and bi+1(1<=i<k), bk and the station, you should find out where to build the two new stations(i.e, choose two blocks bi and bj and make them as new stations) to make the cost as low as possible.

输入:

Standard input will contain multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
The first line of each test case contains an integer N(1<=N<=10000), the number of blocks. N lines follow. The i-th line containing two integers, wi (the weight of garbage of block i, 1<=wi<=10000) and di(the distance between di and di+1, 1<=di<=10000), the last one dk means the distance between dk and the station.

输出:

Standard input will contain multiple test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
The first line of each test case contains an integer N(1<=N<=10000), the number of blocks. N lines follow. The i-th line containing two integers, wi (the weight of garbage of block i, 1<=wi<=10000) and di(the distance between di and di+1, 1<=di<=10000), the last one dk means the distance between dk and the station.

样例输入:

1
4
1 2
2 1
3 3
1 1

样例输出:

3


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!