POJ 1088 滑雪

  

   

    

     

    
    

     

      /***********************************
     
    
   

    

     

    
    

     

      Problem: POJ 1088 滑雪
     
    
   

    

     

    
    

     

      Time: 32MS
     
    
   

    

     

    
    

     

      Memory: 220K
     
    
   

    

     

    
    

     

      Accepted Time: 2009-08-07 18:03:14
     
    
   

    

     

    
    

     

      Tip: 多次DP 
     
    
   

    

     

    
    

     

      ************************************/
     
    
   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #include <string.h>
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int a[109][109],b[109][109],r,c;
     
    
   

    

     

    
    

     
	while(scanf("%d%d",&r,&c)!=EOF)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int i,j;
     
    
   

    

     

    
    

     
		for(i=1;i<=r;i++)
     
    
   

    

     

    
    

     
		for(j=1;j<=c;j++)
     
    
   

    

     

    
    

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

    

     

    
    

     
		memset(b,0,sizeof(b));
     
    
   

    

     

    
    

     
		int temp=(r>c?r:c+1)/2;
     
    
   

    

     

    
    

     
		for(int k=1;k<=temp;k++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			for(i=1;i<=r;i++)
     
    
   

    

     

    
    

     
			for(j=1;j<=c;j++)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(i-1>0&&a[i-1][j]<a[i][j]&&b[i-1][j]+1>b[i][j])
     
    
   

    

     

    
    

     

       b[i][j]=b[i-1][j]+1;
     
    
   

    

     

    
    

     
 if(j-1>0&&a[i][j-1]<a[i][j]&&b[i][j-1]+1>b[i][j])
     
    
   

    

     

    
    

     

       b[i][j]=b[i][j-1]+1;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			for(i=r;i>0;i--)
     
    
   

    

     

    
    

     
			for(j=c;j>0;j--)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(i+1<=r&&a[i+1][j]<a[i][j]&&b[i+1][j]+1>b[i][j])
     
    
   

    

     

    
    

     

       b[i][j]=b[i+1][j]+1;
     
    
   

    

     

    
    

     
 if(j+1<=c&&a[i][j+1]<a[i][j]&&b[i][j+1]+1>b[i][j])
     
    
   

    

     

    
    

     

       b[i][j]=b[i][j+1]+1;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int max=0;
     
    
   

    

     

    
    

     
		for(i=1;i<=r;i++)
     
    
   

    

     

    
    

     
		for(j=1;j<=c;j++)
     
    
   

    

     

    
    

     
		if(max<b[i][j])max=b[i][j];
     
    
   

    

     

    
    

     
		printf("%d/n",max+1);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：万猫学社，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/heihaozi/article/details/4423625