poj 1088ダイナミックプランニング
912 ワード
単純なダイナミックプランニング.
記憶化探索を用いて,各点について上下左右の解を行い,この点の最大値は必ず4方向の中から最大の+1である.
記憶化探索を用いて,各点について上下左右の解を行い,この点の最大値は必ず4方向の中から最大の+1である.
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=105;
int map[maxn][maxn];
int dp[maxn][maxn];
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};
int dfs(int x,int y){
if(dp[x][y])return dp[x][y];
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(map[xx][yy]!=-1&&map[xx][yy]<map[x][y])dp[x][y]=max(dp[x][y],dfs(xx,yy)+1);
}
return dp[x][y];
}
int main(){
int r,c;
while(scanf("%d%d",&r,&c)==2){
memset(map,-1,sizeof(map));
memset(dp,0,sizeof(dp));
for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)scanf("%d",&map[i][j]);
int ans=0;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
ans=max(ans,dfs(i,j));
}
}
printf("%d
",ans+1);
}
}