HDU - 1078 FatMouse and Cheese (dfs + dp)

FatMouse has stored some cheese in a city. The city can be considered as a square grid of dimension n: each grid location is labelled (p,q) where 0 <= p < n and 0 <= q < n. At each grid location Fatmouse has hid between 0 and 100 blocks of cheese in a hole. Now he's going to enjoy his favorite food.

FatMouse begins by standing at location (0,0). He eats up the cheese where he stands and then runs either horizontally or vertically to another location. The problem is that there is a super Cat named Top Killer sitting near his hole, so each time he can run at most k locations to get into the hole before being caught by Top Killer. What is worse -- after eating up the cheese at one location, FatMouse gets fatter. So in order to gain enough energy for his next run, he has to run to a location which have more blocks of cheese than those that were at the current hole.

Given n, k, and the number of blocks of cheese at each grid location, compute the maximum amount of cheese FatMouse can eat before being unable to move.

Input

There are several test cases. Each test case consists of

a line containing two integers between 1 and 100: n and k
n lines, each with n numbers: the first line contains the number of blocks of cheese at locations (0,0) (0,1) ... (0,n-1); the next line contains the number of blocks of cheese at locations (1,0), (1,1), ... (1,n-1), and so on.
The input ends with a pair of -1's.

Output

For each test case output in a line the single integer giving the number of blocks of cheese collected.

Sample Input

3 1
1 2 5
10 11 6
12 12 7
-1 -1

Sample Output

37

题意:

给出 n * n 个洞,每个洞中存了g[i][j]的奶酪,一只老鼠从(1, 1)点出发,可以上下左右走,最多连续走 k 步,然后进入一个洞中吃奶酪,后一次吃到的奶酪数必须大于前一次吃到的奶酪数。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 110;

int n, k;
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int g[N][N];
int dp[N][N];   ///dp[i][j]:以(i, j)为起点的最大值

int dfs(int x, int y)
{
    if(dp[x][y] > 0)
        return dp[x][y];
    dp[x][y] = g[x][y];
    for(int i = 1; i <= k; ++i) ///枚举步数
    {
        for(int j = 0; j < 4; ++j)
        {
            int tx = x + dir[j][0] * i;
            int ty = y + dir[j][1] * i;
            if(tx < 1 || tx > n || ty < 1 || ty > n || g[tx][ty] <= g[x][y])
                continue;
            dp[x][y] = max(dp[x][y], g[x][y] + dfs(tx, ty));
        }
    }
    return dp[x][y];
}

int main()
{
    while(~scanf("%d%d", &n, &k))
    {
        if(n == -1 && k == -1)
        {
            break;
        }
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &g[i][j]);
            }
        }
        memset(dp, 0, sizeof(dp));
        cout<<dfs(1, 1)<<'\n';
    }
    return 0;
}

 

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
qq乃乃好喝到咩噗茶:院校后面加上211标签,放大加粗,招呼语也写上211
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:15
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务