[动态规划] pku1088 记忆化搜索
2 Comments2007.09.02 20:02 by Felicia
简单的记忆化搜索。很早以前做的。
下面是我的代码
下载: pku1088.cpp
#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<n && y>=0 && y<m);
}
int h(int x,int y) {
int i;
if (f[x][y]>0) return 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;
}
#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<n && y>=0 && y<m);
}
int h(int x,int y) {
int i;
if (f[x][y]>0) return 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;
}
Leave a Reply.
吕 | 1F
二月 11th, 2010 at 09:30
你好，我想问一下，for (j=0;j?=h(i,j);这一句中的>?=是什么意思哈？？
Felicia | 2F
二月 19th, 2010 at 15:59
那是一个已经被废弃的运算符
a>?=b
相当于
if (b > a) a = b;