首页 > ACM题库 > HDU-杭电 > hdu 3574 Cube Min Surface Carving待解决[解题报告]C++
2014
11-27

hdu 3574 Cube Min Surface Carving待解决[解题报告]C++

Cube Min Surface Carving

问题描述 :

Given a cube with size x*y*z. each vertex has a non-negative weight w(x, y, z). As shown in figure 1, a surface-carving is a curved section on the XOY plane, and it has two properties:
Buy Sticks

Figure 1. The cube and the surface-carving example

  1. Surface F is formed of x*y vertices, and there is one and only one vertex in each Z axis belonging to the surface.
  2. For each vertex (x, y, z) on the surface,its XOY plane adjacent vertices(x+1, y, z’) or (x-1, y, z’) or (x, y+1, z’) or (x, y-1, z’) satisfy that |z- z’|<=1.
  Define the energy of the surface F as the sum of the vertices value on it.
  Please obtain the minimum value of the surface energy.

输入:

There are multiple test cases. first line input the number of the test case. The number of cases is less than 20.
  For each test case, the first line contains three integers x, y and z(1<=x, y, z<=10), denoting the size of the cube.
  The next x*y*z integers, denoting the weight of each vertex(x, y, z), ordered by the axis X, Y, Z. (eg. w(0,0,0), w(1,0,0), … w(0, 1, 0), … w(0, 0, 1)…w(x,y,z)).

输出:

There are multiple test cases. first line input the number of the test case. The number of cases is less than 20.
  For each test case, the first line contains three integers x, y and z(1<=x, y, z<=10), denoting the size of the cube.
  The next x*y*z integers, denoting the weight of each vertex(x, y, z), ordered by the axis X, Y, Z. (eg. w(0,0,0), w(1,0,0), … w(0, 1, 0), … w(0, 0, 1)…w(x,y,z)).

样例输入:

2

2 2 2
0 5
6 3
4 1
2 7

2 1 5
4 1
4 2
2 3
4 4
4 5

样例输出:

Case 1: 6
Case 2: 4


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮