首页 » 动态规划 » 正文

sdnu 1032 机器人

提交地址:http://www.acmicpc.sdnu.edu.cn/problem/show/1032

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

题解

利用几个特性:
1. 两个机器人的步数相同,那么每个时刻所在的行与列坐标的和相同。
2. 两个机器人不能走在同一个位置,那么他们走的路径不能交叉,所以其中一个机器人的横坐标永远小于另一个。
3. 机器人只能往下和往右。

然后就枚举第一个机器人的横坐标与纵坐标,枚举第二个机器人的横坐标。

代码

代码来自牛客,侵权可联系删除

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 210;
const long long MOD = 1000000007;
typedef long long ll;

int home[55][55];
int dp[55][55][55][55];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            scanf("%d", &home[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            for(int k = 1; k < i; k++)
            {
                int l = i + j - k;//两个机器人走过的曼哈顿距离相同,即:i+j = k+l
                dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l], dp[i][j-1][k][l-1])) + home[i][j] + home[k][l];
            }
    printf("%d\n", dp[n][m-1][n-1][m]);
    return 0;
}

发表评论