POJ 1088スキー記憶化検索(検索+dp)
1015 ワード
問題解決の考え方:
まず検索して、1つの点にアクセスするたびにdpでこの点で滑ることができる最長距離を記録して、次回それにアクセスする時、直接呼び出します
#include
#include
#include
using namespace std;
int a[105][105],dp[105][105];
int f[4][2] = {0,1,1,0,0,-1,-1,0};
int r,c;
int dfs(int j, int k)
{
int ret = 1;
if(dp[j][k]!=-1) return dp[j][k]; // ， dp ？
for(int i=0;i<4;i++)
{
int x = j+f[i][0];
int y = k+f[i][1];
if(x>=1 && x<=r && y>=1 && y<=c && a[x][y]>a[j][k])
{
int ans = dfs(x,y);
ans++;
ret = max(ret, ans);
}
}
return dp[j][k] = ret;
}
int main()
{
while(cin>>r>>c)
{
memset(dp,-1,sizeof(dp));// -1，
for(int i=1; i<=r ;i++)
{
for(int j=1;j<=c;j++)
{
cin>>a[i][j];
}
}
int ma = 0;
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
ma = max(ma , dfs(i,j));
}
}
cout<