题目地址:http://poj.org/problem?id=1088

题目大意:给你一个m*n的矩阵 如果其中一个点高于另一个点 那么就可以从高点向下滑 直到没有可以下滑的时候 就得到一条下滑路径 求最大的下滑路径

分析:因为只能从高峰滑到低峰,无后效性,所以每个点都可以找到自己的最长下滑距离(只与自己高度有关)。记忆每个点的最长下滑距离,当有另一个点的下滑路径遇到这个点的时候,直接加上这个点的最长下滑距离。

dp递推式是,dp[x][y] = max(dp[x][y],dp[x+1][y]+1,dp[x][y-1]+1,dp[x-1][y]+1,dp[x][y+1]+1);

 #include<cstdio>
#include<queue>
#include<algorithm>
//dp[x][y]表示 (x,y)这个点的最长下滑路径
using namespace std;
const int maxn = ;
using namespace std;
int n, m,bx,by,ans;
int G[maxn][maxn];
int dp[maxn][maxn];
int dir[][] = {{,},{,},{,-},{-,}};//这种图的搜索 可以把方向写在一个数组中 使代码更简洁
int dfs(int x, int y)
{
if(dp[x][y])//如果之前已经有结果 那么直接使用
{
return dp[x][y];
}
for(int i = ; i < ;i++)
{
int tx = x,ty = y;
tx += dir[i][];
ty += dir[i][];
// 下面2个if都是排除非法情况
if(tx < || tx >= n || ty < || ty >= m) continue;
if(G[tx][ty] >= G[x][y]) continue;
// 如果四周的点都比自己高 或者路径长没自己长 那么不更新 否则更新为四周的点+1
dp[x][y] = max(dp[x][y],dfs(tx,ty)+);
}
return dp[x][y]; }
int main()
{ scanf("%d %d", &n,&m);
for(int i = ;i < n; i++)
{
for(int j = ; j < m; j++)
{
scanf("%d", &G[i][j]); }
}
ans = ;
for(int i =; i < n; i++)
{
for(int j = ; j < m; j++)
dfs(i,j);
}
for(int i =; i < n; i++)
{
for(int j = ; j < m; j++)
ans = max(ans,dp[i][j]);
}
printf("%d",ans+);//因为自己也算做一步 所以ans+1 return ;
}

最新文章

  1. 为Ubuntu的root设置密码
  2. React Native填坑之旅--布局篇
  3. 代码滑动panorama-即程序中设置SelectedIndex
  4. 关于web服务器访问速度慢的一些简单解决方法
  5. Ubuntu下安装配置JDK 7
  6. 使用Python玩转WMI
  7. tcp/ip的一些概念
  8. CUBRID学习笔记 9 创建示例数据库
  9. js之数组常见的方法
  10. 1023: [SHOI2008]cactus仙人掌图 - BZOJ
  11. android 08 AndroidManifest.xml
  12. hdu 5091 Beam Cannon(扫描线段树)
  13. 拉钩网爬取所有python职位信息
  14. php 好用的函数
  15. base64编码的图片字节流存入html页面中的显示
  16. python 最佳实践与资源汇总
  17. 入门到熟练-Eclipse开发工具
  18. 手工搭建基于ABP的框架(3) - 登录,权限控制与日志
  19. java函数回调
  20. python 库位置

热门文章

  1. [2010国家集训队]Crash的旅游计划
  2. [Usaco2011 Feb]Generic Cow Protests
  3. 题解报告:poj 2533 Longest Ordered Subsequence(最长上升子序列LIS)
  4. Android网络状态监控
  5. C#扩展方法学习
  6. 转-iOS 动画总结----UIView动画
  7. BaseAdapter的优化
  8. struts2 源码地址
  9. IDEA安装使用
  10. 利用nginx与nginx-rtmp-module搭建流媒体服务器实现直播