滑雪
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 64319 | Accepted: 23540 |
Description
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。
Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
Output
输出最长区域的长度。
Sample Input
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
Sample Output
25
题意其实求得是路径上的点数。
解题方法:记忆化DFS 搜索从大到小搜...
#include<cstdio> #include<algorithm> using namespace std; const int MAXN=111; const int INF=-1; #define Min(a,b) (a<b?a:b) #define Max(a,b) (a>b?a:b) int num[MAXN][MAXN],d[MAXN][MAXN]; int p[4][2]={0,1,0,-1,1,0,-1,0}; int R,C; typedef struct Node{ int x,y,val; }; bool operator<(Node a,Node b) { return a.val>b.val?true:false; } void DFS(int x,int y) { int i,j,a,b; int count=0; struct Node queue[4]; for(i=0;i<4;i++) { a=x+p[i][0]; b=y+p[i][1]; if(a>0 && a<=R && b>0 && b<=C && num[a][b]<num[x][y]) { queue[count].x=a; queue[count].y=b; queue[count++].val=num[a][b]; } } if(!count) { d[x][y]=1; return ; } sort(queue,queue+count); for(i=0;i<count;i++) { a=queue[i].x; b=queue[i].y; if(d[a][b]==INF) DFS(a,b); d[x][y]=Max(d[x][y],d[a][b]+1); } } int main() { int i,j,max; while(scanf("%d%d",&R,&C)==2) { for(i=1;i<=R;i++) for(j=1;j<=C;j++) { scanf("%d",&num[i][j]); d[i][j]=INF; } for(i=1;i<=R;i++) for(j=1;j<=C;j++) { if(d[i][j]==INF) DFS(i,j); } max=0; for(i=1;i<=R;i++) for(j=1;j<=C;j++) { max=Max(max,d[i][j]); } printf("%d\n",max); } return 0; }
原来直接DFS记忆化搜索就好了,不明白开始为什么没写对。。。。
#include<cstdio> #include<cstring> using namespace std; #define MAX 105 int f[MAX][MAX]; int map[MAX][MAX]; #define max(a,b) (a>b?a:b) int dp(int x,int y) { if(f[x][y]) return f[x][y]; int tmp=0; if(map[x-1][y]<map[x][y]) tmp=max(tmp,dp(x-1,y)); if(map[x+1][y]<map[x][y]) tmp=max(tmp,dp(x+1,y)); if(map[x][y-1]<map[x][y]) tmp=max(tmp,dp(x,y-1)); if(map[x][y+1]<map[x][y]) tmp=max(tmp,dp(x,y+1)); f[x][y]=tmp+1; return f[x][y]; } int main() { int i,j; int r,c; while(scanf("%d%d",&r,&c)==2) { memset(map,0x3f,sizeof(map)); memset(f,0,sizeof(f)); for(i=1;i<=r;i++) for(j=1;j<=c;j++) scanf("%d",&map[i][j]); for(i=1;i<=r;i++) for(j=1;j<=c;j++) dp(i,j); int res=0; for(i=1;i<=r;i++) for(j=1;j<=c;j++) res=max(res,f[i][j]); printf("%d\n",res); } return 0; }