POJ 1088 sking

我会带着你远行 2022-08-14 01:42 80阅读 0赞

给你个二维数组让你找到这个二维数组的最长下降路径的长度，可以向上下左右四个方向移动。

原来刚看题目是以为是深搜，后来仔细一看发现深搜明显会TLE；就加了记忆化搜索。

坑爹的在写判断越界函数的时候为了，偷懒我把r，c定义为了全局变量，但是忘了注释掉main函数重的r，c定义，于是我一直很好奇我错哪了........

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    const int maxn=105;
    int mov[4][2]={1,0,0,1,-1,0,0,-1};
    
    int high[maxn][maxn],dp[maxn][maxn],r,c;
    
    bool Judge_B(int x,int y){
    	if(x>=0&&x<r&&y>=0&&y<c)
    		return true ;
    	return false;
    }
    
    int dfs(int x,int y){
    	if(dp[x][y]>0)
    		return dp[x][y];
    	int big=0,tmp,tx,ty;
    	for(int i=0;i<4;++i){
    		tx=x+mov[i][0];
    		ty=y+mov[i][1];
    	if(Judge_B(tx,ty))
    	   if(high[x][y]>high[tx][ty]&&big<(tmp=dfs(tx,ty)))
    	   	big=tmp;
    	}
    	dp[x][y]=big+1;
    return dp[x][y];
    }
    
    int main(){
    	while(scanf("%d%d",&r,&c)==2){
    		for(int i=0;i<r;++i)
    			for(int j=0;j<c;++j)
    				scanf("%d",&high[i][j]);
    		memset(dp,0,sizeof(dp));
    		int ans=0,tmp;
    		for(int i=0;i<r;++i)
    			for(int j=0;j<c;++j){
    				tmp=dfs(i,j);
    				if(ans<tmp)
    					ans=tmp;
    			}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj1088 滑雪动态规划+回溯

include<iostream> include<cstdio> using namespace std; int num,n,m,a[100

╰+攻爆jí腚メ/ 2024年02月17日 19:27/ 0 赞/ 52 阅读

相关 POJ 1088 记忆化搜索经典

滑雪 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td> <td>&

红太狼/ 2024年01月22日 06:15/ 0 赞/ 101 阅读

相关 ACM学习-POJ-1088-滑雪

菜鸟学习ACM，纪录自己成长过程中的点滴。学习的路上，与君共勉。 ACM学习-POJ-1088-滑雪 <table style="font-family:Times">

本是古典何须时尚/ 2022年09月07日 14:40/ 0 赞/ 197 阅读

相关 POJ DP 百练1088 滑雪问题

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道

叁歲伎倆/ 2022年08月18日 11:39/ 0 赞/ 179 阅读

相关 POJ 1088 sking

给你个二维数组让你找到这个二维数组的最长下降路径的长度，可以向上下左右四个方向移动。原来刚看题目是以为是深搜，后来仔细一看发现深搜明显会TLE；就加了记忆化搜索。

我会带着你远行/ 2022年08月14日 01:42/ 0 赞/ 81 阅读

相关 poj1088滑雪 (记忆化搜索)

Michael喜欢滑雪这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载

今天药忘吃喽~/ 2022年06月18日 11:28/ 0 赞/ 217 阅读

相关 poj1088滑雪问题

include <stdio.h> int matrix[100][100]; int dp[100][100]; i

ゝ一世哀愁。/ 2022年06月18日 08:38/ 0 赞/ 230 阅读

相关 POJ 1088 动态规划

package p1088; import java.io.File; import java.io.FileNotFoundExceptio

傷城~/ 2022年06月13日 10:49/ 0 赞/ 164 阅读

相关 poj 1088 滑雪

滑雪 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

矫情吗；*/ 2022年06月13日 00:24/ 0 赞/ 212 阅读

相关 dp打开思路3：HDU1069 POJ3616 POJ1088

HDU 1069 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1069][http_acm.hdu.edu.cn_show

Bertha 。/ 2022年05月16日 08:58/ 0 赞/ 182 阅读