POJ 1088 DP=记忆化搜索

话说DP=记忆化搜索这句话真不是虚的。

面对这道题目,题意很简单,但是DP的时候,方向分为四个,这个时候用递推就好难写了,你很难得到当前状态的前一个真实状态,这个时候记忆化搜索就派上用场啦!

通过对四个方向进行搜索,即可得到当前状态的最优解。

#include <iostream>
#include <cstdio>
using namespace std;
int date[][];
int dp[][];
int dir[][]= {{,},{,-},{,},{-,}};
int r,c;
int dpac(int i,int j)
{
if (dp[i][j]>) return dp[i][j];
for (int k=; k<; k++)
{
int nr=i+dir[k][];
int nc=j+dir[k][];
if (nr<||nc<||nr>r||nc>c) continue;
if (date[i][j]>date[nr][nc])
{
dp[nr][nc]=dpac(nr,nc);
dp[i][j]=max(dp[nr][nc]+,dp[i][j]);
} }
return dp[i][j];
}
int main()
{ while (scanf("%d %d",&r,&c)!=EOF)
{
int i,j,k,p;
for (i=; i<=r; i++)
{
for (j=; j<=c; j++)
{
scanf("%d",&date[i][j]);
dp[i][j]=;
}
}
int ans=;
for (i=; i<=r; i++)
{
for (j=; j<=c; j++)
{
int temp=dpac(i,j);
if (ans<temp) ans=temp;
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:Java后台判断请求来自PC端还是移动端


下一篇:centos7下git版本升级及gitlab安装