滑雪[pku oj]

//@PEK DY问题
//最重要的是找到最优子结构,以及构造合理的结束函数。
//自己现在最大的问题是在利用备忘录的递归还是迭代上找不准。本题采用的是备忘录递归,但是在处理上还有很多重复的。
//本题应该是可以向贪心算法上改进的。
//在构造最优子结构问题上也欠缺经验,本题主要花费在了这上面。
//本题因为freopen()提交的时候没注释掉,dp()中right的坐标写错了。导致了2次WA。
#include<cstdio>
#include
<cstdlib>
#include
<algorithm>
using namespace std;

#define N 102
#define INF 12000
int data[N][N];
int len[N][N];
int rt,ct;
int dp(int r, int c);
int GetMax(int a,int b,int c,int d);

int main()
{
    freopen(
"input.txt","r",stdin);
    
while(~scanf("%d %d",&rt,&ct)){
        
for(int i=1;i<=rt;i++)
            
for(int j=1;j<=ct;j++)
                scanf(
"%d",&data[i][j]);
        
for(int j=0;j<=ct+1;j++)
        {
            data[
0][j]=INF;
            data[rt
+1][j]=INF;
        }
        
for(int j=0;j<=rt+1;j++)
        {
            data[j][
0]=INF;
            data[j][ct
+1]=INF;
        }

        
for(int i=1;i<=rt;i++)
            
for(int j=1;j<=ct;j++)
                len[i][j]
=-1;

        
for(int i=1;i<=rt;i++)
            
for(int j=1;j<=rt;j++)
                dp(i,j);

        
int max=len[1][1];
        
for(int i=1;i<=rt;i++)
            
for(int j=1;j<=ct;j++)
                
if(max<len[i][j])
                    max
=len[i][j];
        printf(
"%d\n",max);
    }
//end while
    return 0;
}

int dp(int r, int c)
{
    
bool left=data[r][c]<=data[r][c+1];
    
bool right=data[r][c]<=data[r][c-1];
    
bool down=data[r][c]<=data[r+1][c];
    
bool up=data[r][c]<=data[r-1][c];

    
if(left && right && down && up)
        
return len[r][c]=1;
    
else
    {
        
int dipl=1,dipr=1,dipd=1,dipu=1;
        
if(!left)
        {
            dipl
+=(len[r][c+1]!=-1? len[r][c+1] : dp(r,c+1);
        }
        
if(!down)
        {
            dipd
+=(len[r+1][c]!=-1? len[r+1][c] : dp(r+1,c);
        }
        
if(!right)
        {
            dipr
+=(len[r][c-1]!=-1? len[r][c-1] : dp(r,c-1);
        }
        
if(!up)
        {
            dipu
+=(len[r-1][c]!=-1? len[r-1][c] : dp(r-1,c);
        }
        
return len[r][c]=GetMax(dipl,dipr,dipd,dipu);
    }
}
    
int GetMax(int a,int b,int c,int d)
{
    
return max(a,max(b,max(c,d)));
}

posted on 2012-02-25 21:08 DjvuLee 阅读(728) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


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


导航

<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

统计

常用链接

留言簿

随笔分类(13)

随笔档案(19)

文章分类(2)

文章档案(1)

搜索

最新评论

评论排行榜