话说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 ;
}

最新文章

  1. 在Java中直接调用js代码(转载)
  2. IOS开发UI基础 UIDatePicker的属性
  3. 快捷键forMac
  4. 业务对象(BO)设计
  5. 使用qmake生成Makefile
  6. UVa 11292 - Dragon of Loowater(排序贪心)
  7. TIMESTAMP类型字段在SQL Server和MySQL中的含义和使用
  8. EC20指令测试
  9. Javascript继承1:子类的的原型对象----类式继承
  10. Async/Await是这样简化JavaScript代码的
  11. Django之--通过MVC架构的html模板展示Hello World!
  12. Financiers Game CodeForces - 737D (博弈论)
  13. vue-concise-slider 一个轻量的vue幻灯片组件
  14. Spring Boot 介绍
  15. JDBC 连Sql Server 接数据库--The TCP/IP connection to the host localhost, port 1433 has failed
  16. Python开发【Django】:Model操作(二)
  17. NSJSONSerialization能够处理的JSONData
  18. 导入项目@Override报错原因及解决办法
  19. js 时间对比
  20. 安装Eclipsemaven插件

热门文章

  1. 059、Java中定义一个有参数无返回值的方法
  2. 初学Java(1)
  3. 吴裕雄 Bootstrap 前端框架开发——Bootstrap 字体图标(Glyphicons):glyphicon glyphicon-fast-forward
  4. POJ 3468 区间更新(求任意区间和)A Simple Problem with Integers
  5. Oracle rownum用法、分页
  6. 自己安装windows版本的Flink
  7. qt 中使用 c 语言文件
  8. spring boot配置druid连接池连接mysql
  9. spring boot 连接Mysql介绍
  10. 前端第三篇---前端基础之JavaScript