HDU1078 FatMouse and Cheese

2017年8月13日

一只老鼠在一个n*n的地图上吃食物,每次只能垂直或者水平走,且所走的格子上的食物必须大于当前所在格子的食物,每次前进,可以只走一格,也可以跳着走k格,最大不能超过k,问你老鼠所能吃到的食物是多少.

DP 跟 DFS 的结合,定义dp[x][y]为走到坐标(x, y)所能吃到的最大食物,那么就可以有 dp[x][y] = max(dp[nx][ny] | nx, ny 为从x出发所有能到达点的坐标) + map[x][y].用 DFS 就可以把问题解决了,最后答案就是 dp[1][1],表示从初始位置出发所能吃到的最大食物量.

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1078

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
int a[N][N];
int dp[N][N];
int n, k;
int dfs(int x, int y)
{
    if (dp[x][y])
        return dp[x][y];
    int mx = 0;
    for (int i = 1; i <= k; i++) {
        for (int z = 0; z < 4; z++) {
            int nx = x + dx[z] * i, ny = y + dy[z] * i;
            if (1 <= nx && nx <= n && 1 <= ny && ny <= n) {
                if (a[nx][ny] > a[x][y]) {
                    mx = max(mx, dfs(nx, ny));
                }
            }
        }
    }
    return dp[x][y]  = a[x][y] + mx;
}
int main()
{
    while (~scanf("%d %d", &n, &k) && (n != -1 && k != -1)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        printf("%d\n", dfs(1, 1));
    }
    return 0;
}
去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注