hdu 1078 （dp记忆化搜索）

清疚 2022-08-20 13:26 144阅读 0赞

题意：有一个n\*n的方格，每个格子有一个价值，经过这个格子就可以得到这个价值，每次可以横着或者竖着一步最多走K格，并且每次走的格子要比上一个格子的价值大，问现在从位置(1,1)走，最大可以获得的价值.

分析：

记忆化搜素，dp\[i\]\[j\]表示的是从位置(i,j)开始走可以获得的最大价值。记录下这些价值就可以了。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 105;
    
    int dp[maxn][maxn],s[maxn][maxn];
    //dp[i][j]表示起点为(i,j)是获得的最大价值
    int n,k;
    int t[4][2]={1,0,-1,0,0,1,0,-1};
    
    int dfs(int x,int y)
    {
        int maxx=0;
        if(!dp[x][y])
        {
            for(int i=1;i<=k;i++)
            {
                for(int j=0;j<4;j++)
                {
                    int xx=x+t[j][0]*i;
                    int yy=y+t[j][1]*i;
                    if(xx>=0&&xx<n&&yy>=0&&yy<n&&s[xx][yy]>s[x][y])
                    {
                        int ans=dfs(xx,yy);
                        if(ans>maxx)
                        {
                            maxx=ans;
                        }
                    }
                }
            }
            dp[x][y]=maxx+s[x][y];
        }
        return dp[x][y];
    }
    int main()
    {
        while(scanf("%d%d",&n,&k)==2)
        {
            if(n==-1&&k==-1)break;
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    scanf("%d",&s[i][j]);
                }
            }
            memset(dp,0,sizeof(dp));
            int sum=dfs(0,0);
            printf("%d\n",sum);
        }
        return 0;
    }