posts - 14,  comments - 4,  trackbacks - 0

         前段时间写了PKU的滑雪,因为是中文的比较好动,想了一下直接过了,就像Mr_cai说的所谓记忆化搜索就是 搜索+动态规划。记录每一个点为起点开始滑的最大值,然后遇到有记录的坐标就直接返回坐标上的值。
         后来又去做HDU 的FatMouse and Cheese,英文描述。没注意细节,与前一题不一样的地方在于这题可以直着走<=K步,一旦停下来下一次又可以走<=K步。最后才知道的,还有就是老鼠每次都是从坐标0,0出发。。居然没看见,,导致我用了上面一样的方法每个坐标搜一次,超时,直到最后才发现这两个问题,可见仔细有多重要。

#include <iostream>
#include 
<cstring>
using namespace std;
int map[102][102];
int ans[102][102];
int n,m;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int dfs(int x,int y)
{
    
if(ans[x][y]) return ans[x][y];
    
int i,j,nx,ny;
    
int temp,maxv=0;
    
for(i=0;i<4;++i)
    
{
        
for(j=1;j<=m;++j)
        
{
            nx 
= x+dir[i][0]*j;
            ny 
= y+dir[i][1]*j;
            
if(nx>=1 && nx<=&& ny>=1 && ny<=&& map[nx][ny] > map[x][y])
            
{
                temp 
= dfs(nx,ny);
                
if (temp > maxv)
                
{
                    maxv 
= temp;
                }

            }

        }

    }

    ans[x][y]
=maxv+map[x][y];
    
return ans[x][y];
}


int main()
{
    
int i,j;
    
while(~scanf("%d%d",&n,&m))
    
{
        
if(n==-1 && m==-1)break;
        memset(ans,
0,sizeof(ans));
        memset(map,
10,sizeof(map));
        
for(i=1;i<=n;++i)
        
{
            
for(j=1;j<=n;++j)
            
{
                scanf(
"%d",&map[i][j]);
            }

        }

        dfs(
1,1);
        printf(
"%d\n",ans[1][1]);
    }

    
return 0;
}


 


 

posted on 2011-04-15 13:55 mr_chen 阅读(190) 评论(0)  编辑 收藏 引用 所属分类: 搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔档案(14)

文章分类(8)

文章档案(11)

搜索

  •  

最新评论

阅读排行榜

评论排行榜