hdu 1078 FatMouse and Cheese（记忆搜）

N*N的矩阵，每个格子上有一个值。

老鼠起始在（1，1），每次只能水平着走或垂直着走。且最多只能走K步。且走到的格子里的值必须比上一次呆的格子里的值大。

问老鼠最多收集到多少值。

思路：

记忆搜好写、方便。

注意边界

代码：

int n,k;

int a[105][105];

int dp[105][105];

int dfs(int x,int y){

    if(dp[x][y]>0)

        return dp[x][y];

    for(int i=x+1;i<=min(n,x+k);++i){

        if(a[i][y]>a[x][y]){

            dp[x][y]=max( dp[x][y],dfs(i,y)+a[x][y] );

        }

    }

    for(int i=x-1;i>=max(1,x-k);--i){

        if(a[i][y]>a[x][y]){

            dp[x][y]=max( dp[x][y],dfs(i,y)+a[x][y] );

        }

    }

    for(int i=y+1;i<=min(n,y+k);++i){

        if(a[x][i]>a[x][y]){

            dp[x][y]=max( dp[x][y],dfs(x,i)+a[x][y] );

        }

    }

    for(int i=y-1;i>=max(1,y-k);--i){

        if(a[x][i]>a[x][y]){

            dp[x][y]=max( dp[x][y],dfs(x,i)+a[x][y] );

        }

    }

    if(dp[x][y]==0)

        dp[x][y]=a[x][y];

    return dp[x][y];

}

int main(){

    while(scanf("%d%d",&n,&k)!=EOF){

        if(n==-1 && k==-1){

            break;

        }

        rep(i,1,n){

            rep(j,1,n){

                scanf("%d",&a[i][j]);

            }

        }

        mem(dp,0);

        int ans=dfs(1,1);

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

hdu 1078 FatMouse and Cheese（记忆搜）

最新文章

热门文章