HDU-1078

2018-03-04

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1078

题目大意

有一只老鼠在一个n*n的地图上跑，只能水平或竖直跑，最多一次跑k步，每停到一个位置，就要吃掉当前位置的全部奶酪，并且要求每一次停的位置的奶酪数必须大于上一次停的位置的奶酪数。问最大能吃多少块奶酪。

思想

显然会用到搜索，当直接写一个搜索的时候会TLE，所以考虑记忆化搜索。向后记忆，例如，当卡走到了(x1,y1)这个点，不论前面是怎么到这个点的，从这个点向后走都是一样的。所以假设这个点已经走过了，那么就不需要再重新搜索一遍了，只需要把答案返回回去。
我们这里开辟dp[i][j]表示从(i,j)点开始搜索能吃到的最大奶酪数，mmap[i][j]表示该点的奶酪数。
状态转移方程：dp[i][j]=max(dp[x][y])+mmap[i][j],(x,y)为所有能一次到达(i,j)的坐标。

代码

HDU-1078

#include<cstdio>
#include<cstring>
using namespace std;
int n,k;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int dp[105][105],mmap[105][105];
int dfs(int x,int y)
{
    if (dp[x][y]) return dp[x][y];
    dp[x][y]=mmap[x][y];
    int mmax=0;
    for (int kk=1;kk<=k;kk++)
    {
        for (int dir=0;dir<4;dir++)
        {
            int xx=x+dx[dir]*kk;
            int yy=y+dy[dir]*kk;
            if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
            if (mmap[xx][yy] <= mmap[x][y]) continue;
            int nn=dfs(xx,yy);
            if (mmax < nn) mmax=nn;
        }
    }
    dp[x][y]+=mmax;
    return dp[x][y];
}
int main()
{
    while (scanf("%d%d",&n,&k) && n!=-1 && k!=-1)
    {
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                scanf("%d",&mmap[i][j]);
        memset(dp,0,sizeof(dp));
        printf("%d\n",dfs(0,0));
    }
}

后记

这个题有点坑，，前面写了一发bfs结果tle了。。于是心态崩了去打soul knight。。。输的回来继续写代码。。。天意天意。。。。