voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0
	我们学校的ACM网站进不去了。。。
 	滑雪,这个题目是稍微复杂一些的动态规划题,基本思路是先求的一个点上,上下左右上的最优值,然后再做判断。。该题一定要抓住这种思想,不然会很迷惑。
在代码实现的时候,用了一个中间值temp,用来存贮最优解。。。
代码如下:
#include<stdio.h>
#include
<string.h>
int s[101][101],map[101][101];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int n,m;
int dfs(int x,int y)            //计算x,y点上的最大深度,事实上它可以计算出所有他可以到达点上的最优值
{
    
int sum=0;
    
int temp=0;
    
int i,x0,y0;
    
if(s[x][y]!=0)
        
return s[x][y];
    
for(i=0;i<4;i++)        //从上下左右四个最优值中选择
    {
        x0
=d[i][0]+x;
        y0
=d[i][1]+y;
        temp
=1;                //最小深度为1。。
        if((map[x0][y0]<map[x][y])&&x0>=0&&y0>=0&&x0<n&&y0<m)//满足条件的点,重置temp
        {
            temp
=dfs(x0,y0)+1;
        }

        
if(temp>sum)                //更新最大深度
        {
            sum
=temp;
        }

    }

    s[x][y]
=sum;                //置最优值
    return sum;                    //返回最优值
}

int main()
{
    
int sum,i,j;
    
while(scanf("%d %d",&n,&m)!=EOF)
    
{
        memset(s,
0,sizeof(s));
        sum
=0;
        
for(i=0;i<n;i++)
            
for(j=0;j<m;j++)
                scanf(
"%d",&map[i][j]);
        
for(i=0;i<n;i++)
            
for(j=0;j<m;j++)
            
{
                dfs(i,j);
            }

        
for(i=0;i<n;i++)
        
{
            
for(j=0;j<m;j++)
            
{
                
if(s[i][j]>sum)
                    sum
=s[i][j];
                
//printf("%d ",s[i][j]);
            }

        
//    printf("\n");
        }

        printf(
"%d\n",sum);
    }

    
return 0;
}


      这段代码可能是我自己写的,我记得当时我不理解这个,网上找了很多代码来看,结果还是看不懂。。。现在我看着这段代码还是觉得虚,虽然我理解他的意思。。。总结经验我觉得以前没有好好理解这个题目,然后盲目的看代码,结果毁了这个题目!!!以后一定要抓住思路再写代码!!!其实这个题目可以看做是最长不下降子序列扩展到二维的情况!!可能这也是我解决不了这个题目的一个因素,除了思路不清晰外,在写代码的时候直接用最优数组去迭代是不能成功的!!要用到中间变量!!最后总结为:1、盲目看\写代码。。2、经验主义。。
posted on 2010-09-17 10:29 jince 阅读(482) 评论(0)  编辑 收藏 引用

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


哈哈哈哈哈哈