本文主要是介绍hdu(1078) FatMouse and Cheese (记忆化搜索+dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*第一次用记忆化搜索，
其实并不难，只不过在搜索的同时记住了在各个坐标的权值。
在这里题意是；在一个n*n的矩阵里，值是权值，在竖直或水平方向上
行走1--k步，全只要递增，不能重复走，到最后使其总权值和最大。
说白了就是找一个递增序列，使其总和值最大。。
*/
这一题综合了DFS和DP，很好的一道题。dp[i][j]表示以第i行第j列个
网格为起点所能得到的最大值，需要注意的是一次最多走k步必须在
一条直线上，这个只需要在普通的深搜上加一层循环表示从1步到k步，
状态转移就是
dp[i][j] = max{dp[i + d1*c][j + d2*c], 1=< c <= k} + map[i][j]。
#include"stdio.h"
#include"string.h"
int a[101][101];
int dp[101][101];
int dir[4][2]={-1,0, 0,1, 1,0, 0,-1};
int n,m;
int judge(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<n)
return 1;
return 0;
}
int bfs(int x,int y)
{
int i,j,xx,yy,temp,max=0;
if(dp[x][y])//说明前面已经走过了。。
return dp[x][y];
for(i=0;i<4;i++)
for(j=1;j<=m;j++)
{
xx=x+dir[i][0]*j;
yy=y+dir[i][1]*j;
if(judge(xx,yy)&&a[xx][yy]>a[x][y])
{
temp=bfs(xx,yy);
if(temp>max)
max=temp;
}
}
dp[x][y]=a[x][y]+max;
return dp[x][y];
}
int main()
{
int i,j;
while(scanf("%d%d",&n,&m),n!=-1&&m!=-1)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
memset(dp,0,sizeof(dp));
bfs(0,0);
printf("%d\n",dp[0][0]);
}
return 0;
}
这篇关于hdu(1078) FatMouse and Cheese (记忆化搜索+dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
