首页 > ACM题库 > HDU-杭电 > HDU 1578 Martian Mining-递推-[解题报告] C++
2013
12-12

HDU 1578 Martian Mining-递推-[解题报告] C++

Martian Mining

问题描述 :

The NASA Space Center, Houston, is less than 200 miles from San Antonio, Texas (the site of the ACM Finals this year). This is the place where the astronauts are trained for Mission Seven Dwarfs, the next giant leap in space exploration. The Mars Odyssey program revealed that the surface of Mars is very rich in yeyenum and bloggium. These minerals are important ingredients for certain revolutionary new medicines, but they are extremely rare on Earth. The aim of Mission Seven Dwarfs is to mine these minerals on Mars and bring them back to Earth.

The Mars Odyssey orbiter identified a rectangular area on the surface of Mars that is rich in minerals. The area is divided into cells that form a matrix of n rows and m columns, where the rows go from east to west and the columns go from north to south. The orbiter determined the amount of yeyenum and bloggium in each cell. The astronauts will build a yeyenum refinement factory west of the rectangular area and a bloggium factory to the north. Your task is to design the conveyor belt system that will allow them to mine the largest amount of minerals.


There are two types of conveyor belts: the first moves minerals from east to west, the second moves minerals from south to north. In each cell you can build either type of conveyor belt, but you cannot build both of them in the same cell. If two conveyor belts of the same type are next to each other, then they can be connected. For example, the bloggium mined at a cell can be transported to the bloggium refinement factory via a series of south-north conveyor belts.

The minerals are very unstable, thus they have to be brought to the factories on a straight path without any turns. This means that if there is a south-north conveyor belt in a cell, but the cell north of it contains an east-west conveyor belt, then any mineral transported on the south-north conveyor beltwill be lost. The minerals mined in a particular cell have to be put on a conveyor belt immediately, in the same cell (thus they cannot start the transportation in an adjacent cell). Furthermore, any bloggium transported to the yeyenum refinement factory will be lost, and vice versa.

Your program has to design a conveyor belt system that maximizes the total amount of minerals mined,i.e., the sum of the amount of yeyenum transported to the yeyenum refinery and the amount of bloggium transported to the bloggium refinery.

输入:

The input contains several blocks of test cases. Each case begins with a line containing two integers: the number 1 ≤ n ≤ 500 of rows, and the number 1 ≤ m ≤ 500 of columns. The next n lines describe the amount of yeyenum that can be found in the cells. Each of these n lines contains m integers. The first line corresponds to the northernmost row; the first integer of each line corresponds to the westernmost cell of the row. The integers are between 0 and 1000. The next n lines describe in a similar fashion theamount of bloggium found in the cells.

The input is terminated by a block with n = m = 0.

输出:

For each test case, you have to output a single integer on a separate line: the maximum amount of mineralsthat can be mined.

样例输入:

4 4
0 0 10 9
1 3 10 0
4 2 1 3 
1 1 20 0
10 0 0 0
1 1 1 30
0 0 5 5
5 10 10 10
0 0

样例输出:

98

Hint
Hint
Huge input file, 'scanf' recommended to avoid TLE.

题意:如下图,有一种n*m的网格,每个格子里可能分别有两种矿物a[i][j]和b[i][j],在网格的上边和左边分别有这两种矿物的收集站。对每个网格,可以建立向上或者向左的传送带,将该格所有矿物传送。但是,传送带不能变方向,否则变方向之前的矿物会从传送带上掉落下来。比如,矿物如果从(i,j)传送到(i,j-1),再传送到(i-1,j-1),就会掉落。问最终能收集到的矿物最多为多少(两种矿物数量之和)。

解法:首先,对于第(i,j)格,如果它向左传送,则应该让(i,0), (i,1)…(i,j-1)都向左传送。向上同理。

   设d[i][j][0]表示第(i,  j)格向左传送的情况下,矩形(0,0)-(i,j)所能收集到最多的矿石数,d[i][j][1]表示第(i,  j)格向上传送的情况下,矩形(0,0)-(i,j)所能收集到最多的矿石数。设wes[i][j]表示收集点在左边的矿石(i,0),(i,1)…(i,j)格共有多少,nor[i][j]表示收集点在上边的矿石(0,j),(1,j),(2,j)…(i,j)格共有多少。

   wes和nor数组递推易求,d数组的状态转移方程为:d[i][j][0] = wes[i][j] + max(d[i-1][j][0], d[i-1][j][1]),d[i][j][1] = nor[i][j] + max(d[i][j-1][0], d[i][j-1][1])。

tag:网格类dp

/*
  * Author:  Plumrain
  * Created Time:  2013-11-18 17:03
  * File Name: DP-POJ-2948.cpp
  */
 #include <iostream>
 #include <cstdio>
 #include <cstring>
 
 using namespace std;
 
 #define CLR(x) memset(x, 0, sizeof(x))
 
 int n, m;
 int d[505][505][2];
 int x[505][505][2];
 int nor[505][505], wes[505][505];
 
 void init()
 {
     for (int t = 0; t < 2; ++ t)
         for (int i = 0; i < n; ++ i)
             for (int j = 0; j < m; ++ j)
                 scanf ("%d", &x[i][j][t]);
 
     CLR (nor); CLR (wes);
     for (int i = 0; i < n; ++ i)
         for (int j = 0; j < m; ++ j){
             wes[i][j] = (j ? x[i][j][0]+wes[i][j-1] : x[i][j][0]);
             nor[i][j] = (i ? x[i][j][1]+nor[i-1][j] : x[i][j][1]);
         }
 }
 
 int DP()
 {
     CLR (d);
     d[0][0][0] = x[0][0][0]; d[0][0][1] = x[0][0][1];
     for (int i = 0; i < n; ++ i)
         for (int j = 0; j < m; ++ j){
             if (!i && !j) continue;
             d[i][j][0] = wes[i][j];
             if (i)
                 d[i][j][0] += max(d[i-1][j][0], d[i-1][j][1]);
             d[i][j][1] = nor[i][j];
             if (j)
                 d[i][j][1] += max(d[i][j-1][0], d[i][j-1][1]);
         }
     return max(d[n-1][m-1][0], d[n-1][m-1][1]);
 }
 
 int main()
 {
     while (scanf ("%d%d", &n, &m) != EOF && n){    
         init();
         printf ("%d\n", DP());        
     }
     return 0;
 }

 

解题报告转自:http://www.cnblogs.com/plumrain/p/POJ_2948.html