首页 > 代码库 > HDU 1078 dfs+dp

HDU 1078 dfs+dp

2024-07-21 14:52:29   217人阅读

题目大意：

在n*n的矩阵中，每个格子放置了一定数量的食物，一只老鼠每次水平或竖直最多移动k格，每次到的位置食物都要比前一次多，问最后一共能得到多少食物

 

这道题利用记忆化搜索做，利用nowstate不断记录下一个位置所能到达的最大值，利用nowstate+mat[i][j](当前区域中所含的食物数量)得到dfs的值

 

每次dfs返回的都是当前点到最终结点所能得到的食物总量

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define N 102 7 int mat[N][N],dp[N][N],k,n; 8 int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; 9 int dfs(int x,int y)//dfs得到的是当前点到终点总共采集的食物总量10 {11     if(dp[x][y]) return dp[x][y];12     int nowstate=0;13     for(int i=1;i<=k;i++){14         for(int j=0;j<4;j++){15             int xx=x+dir[j][0]*i;16             int yy=y+dir[j][1]*i;17             if(xx>=0&&xx<n&&yy>=0&&yy<n){18                 if(mat[xx][yy]>mat[x][y]){19                     nowstate=max(nowstate,dfs(xx,yy));20                 }21             }22         }23 24     }25     dp[x][y]=nowstate+mat[x][y];26     return dp[x][y];27 }28 int main()29 {30     while(scanf("%d%d",&n,&k)){31         memset(dp,0,sizeof(dp));32 33         if(n==-1&&k==-1)34             break;35 36         for(int i=0;i<n;i++)37             for(int j=0;j<n;j++)38                 scanf("%d",&mat[i][j]);39 40         int ans=dfs(0,0);41         printf("%d\n",ans);42     }43     return 0;44 }

 

HDU 1078 dfs+dp


联系
我们