简单的记忆化搜索。很早以前做的,代码风格很乱。将就一下啦。

#include <stdio.h>
#include 
<string.h>
const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int a[100][100],f[100][100],n,m,i,j,max;
int ok(int x,int y) {
    
return (x>=0 && x<&& y>=0 && y<m);
}

int h(int x,int y) {
    
int i;
    
if (f[x][y]>0return f[x][y];
    
for (i=0;i<4;i++if (ok(x+dx[i],y+dy[i]) && a[x+dx[i]][y+dy[i]]<a[x][y]) f[x][y]>?=h(x+dx[i],y+dy[i])+1;
    
return f[x][y];
}

int main() {
    
for (scanf("%d%d",&n,&m),memset(f,0,sizeof(f)),i=0;i<n;i++for (j=0;j<m;j++) scanf("%d",&a[i][j]);
    
for (max=0,i=0;i<n;i++for (j=0;j<m;j++) max>?=h(i,j);
    printf(
"%d\n",max+1);
    
return 0;
}
posted on 2007-09-02 20:02 Felicia 阅读(914) 评论(5)  编辑 收藏 引用 所属分类: 动态规划
Comments
  • # re: [动态规划]pku1088
    代川
    Posted @ 2007-10-11 14:31
    大牛啊  回复  更多评论   
  • # re: [动态规划]pku1088
    Felicia
    Posted @ 2007-10-11 15:36
    @代川
    莫鄙视我……  回复  更多评论   
  • # re: [动态规划]pku1088
    小白菜
    Posted @ 2008-09-14 08:27
    美女啊,想法很好啊!  回复  更多评论   
  • # re: [动态规划]pku1088[未登录]
    frank
    Posted @ 2009-09-10 16:19
    max>?=h(i,j);怎么编译通不过呢?
    你的思想太好了!  回复  更多评论   
  • # re: [动态规划]pku1088
    Isun
    Posted @ 2009-09-20 01:40
    新版G++不支持这个操作符了。
    a>?=b 等价于 a = max(a, b) @frank
      回复  更多评论   

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