SDNU 1032.机器人

1032.机器人

Time Limit: 1000 MS Memory Limit: 65536 KB
Total Submission(s): 110 Accepted Submission(s): 55

Description
SYC喜欢宅在家里,但又不喜欢清理垃圾,有一天实在看不下去了,就把好友ZZK和LG叫来帮忙。没想到他俩更懒,把各自的机器人带过来了,当然,大家都不愿意为这两台机器人设计程序,所以请你来帮忙。

为了运算的简单,我们将SYC的屋子看做N*M的矩阵,在矩阵的每一个坐标上都可能有不同数量的垃圾。已知开始时这两个机器人都放在矩阵的左上角,两个机器人每次都只能向右或向下走一步,而且不能向回走,也不能走另一个机器人走过的坐标。现在请你帮忙,计算这两个机器人都走到右下角时打扫垃圾的最大数量。

Input
第一行有两个整数N和M,分别表示SYC家占地N行M列。1<=N,M<=50。
接下来有N行,每行有M个数据,表示N*M的矩阵,每行各个数字使用空格分隔。矩阵第i行j列的数字表示该处垃圾的个数(不超过1000)。

Output
输出打扫垃圾的最大数量

Sample Input
3 3
0 9 9
6 1 8
2 3 0

Sample Output
37

题解:
这题和 sdnuoj 1194 是一样的,都是四维 dp 的板子题(甚至交一样的代码都能Ac)。dp 这个东西不太好解释,毕竟是板子题,还是很好去理解的,看看应该就懂了。

Ac代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int ma[53][53];
int dp[53][53][53][53];

int main()
{
int n,m;
cin >> n >> m;
memset(ma,0,sizeof(ma));
memset(dp,0,sizeof(dp));
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
cin >> ma[i][j];
}
}
int x_1,y_1,x_2,y_2;
for(x_1 = 1; x_1 <= n; x_1++)
{
for(y_1 = 1; y_1 <= m; y_1++)
{
for(x_2 = 1; x_2 <= n; x_2++)
{
for(y_2 = 1; y_2 <= m; y_2++)
{
dp[x_1][y_1][x_2][y_2] = max(dp[x_1][y_1][x_2][y_2],dp[x_1 - 1][y_1][x_2 - 1][y_2]);
dp[x_1][y_1][x_2][y_2] = max(dp[x_1][y_1][x_2][y_2],dp[x_1 - 1][y_1][x_2][y_2 - 1]);
dp[x_1][y_1][x_2][y_2] = max(dp[x_1][y_1][x_2][y_2],dp[x_1][y_1 - 1][x_2 - 1][y_2]);
dp[x_1][y_1][x_2][y_2] = max(dp[x_1][y_1][x_2][y_2],dp[x_1][y_1 - 1][x_2][y_2 - 1]);
if(x_1 == x_2 && y_1 == y_2)
{
dp[x_1][y_1][x_2][y_2] += ma[x_1][y_1];
}
else
{
dp[x_1][y_1][x_2][y_2] += ma[x_1][y_1] + ma[x_2][y_2];
}
}
}
}
}
cout << dp[n][m][n][m] << endl;
return 0;
}
我好饿呀!求打赏!