P1434 [SHOI2002]滑雪

admin

https://www.luogu.org/problemnew/show/P1434
题目描述
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（从24开始，在1结束）。当然25－24－23―┅―3―2―1更长。事实上，这是最长的一条。

输入输出格式
输入格式：
输入的第一行为表示区域的二维数组的行数R和列数C（1≤R，C≤100）。下面是R行，每行有C个数，代表高度(两个数字之间用1个空格间隔)。

输出格式：
输出区域中最长滑坡的长度。

输入输出样例
输入样例#1：
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
输出样例#1：
25

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. using namespace std;
    
12. int n,m,jl=0,f[200][200],b[200][200],px[4]={0,0,1,-1},py[4]={1,-1,0,0},maxn=-0x3f3f3f3f;
    
13. struct hehe
    
14. {
    
15.         int hei,x,y;
    
16. }a[40000];
    
17. bool cmp(hehe x,hehe y)
    
18. {
    
19.         return x.hei<y.hei;
    
20. }
    
21. bool check(int x,int y,int w)
    
22. {
    
23.         if(x<=0||y<=0||x>n||y>m||b[x][y]>=w) return false;
    
24.         return true;
    
25. }
    
26. int main()
    
27. {
    
28.         scanf("%d%d",&n,&m);
    
29.         for(int i=1;i<=n;i++)
    
30.                 for(int j=1;j<=m;j++)
    
31.                         f[i][j]=1;
    
32.         for(int i=1;i<=n;i++)
    
33.                 for(int j=1;j<=m;j++)
    
34.                         scanf("%d",&a[++jl].hei),a[jl].x=i,a[jl].y=j,b[i][j]=a[jl].hei;
    
35.         sort(a+1,a+1+jl,cmp);
    
36.         for(int i=1;i<=jl;i++)
    
37.                 for(int j=0;j<4;j++)
    
38.                         if(check(a[i].x+px[j],a[i].y+py[j],a[i].hei))
    
39.                                 f[a[i].x][a[i].y]=max(f[a[i].x][a[i].y],f[a[i].x+px[j]][a[i].y+py[j]]+1);
    
40.         for(int i=1;i<=n;i++)
    
41.                 for(int j=1;j<=m;j++)
    
42.                         maxn=max(maxn,f[i][j]);
    
43.         printf("%d",maxn);
    
44.         return 0;
    
45. }

复制代码

倚窗倾听风吹雨

记忆化搜索

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. const int M=110;
   
5. int m,n,a[M][M],dr[4]={0,-1,0,+1},dc[4]={-1,0,+1,0},lens[M][M],ans;
   
6. int dfs(int x,int y)
   
7. {
   
8.     if(x<=0 || y<=0 || x>=m+1 || y>=n+1)return 0;
   
9.     int k=0;
   
10.     if(lens[x][y]!=1)return lens[x][y];
    
11.     for(int i=0;i<=3;i++)
    
12.       if(a[x][y]>a[x+dr[i]][y+dc[i]])
    
13.           k=max(k,dfs(x+dr[i],y+dc[i])+1);
    
14.     lens[x][y]=max(lens[x][y],k);
    
15.     return lens[x][y];
    
16. }
    
17. int main()
    
18. {
    
19.     cin>>m>>n;
    
20.     for(int i=1;i<=m;i++)
    
21.         for(int j=1;j<=n;j++)
    
22.         {
    
23.             cin>>a[i][j];
    
24.             lens[i][j]=1;
    
25.         }
    
26. 
    
27.     for(int i=1;i<=m;i++)
    
28.         for(int j=1;j<=n;j++)
    
29.             ans=max(ans,dfs(i,j));
    
30.     cout<<ans<<endl;
    
31.     return 0;
    
32. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int r,c,len=1;
   
5. struct ha
   
6. {
   
7.     int h,x,y;
   
8. }f[10001];
   
9. int l[101][101],h[101][101];
   
10. bool operator< (ha p,ha q)
    
11. {
    
12.     return p.h>q.h;
    
13. }
    
14. int dx[4]={-1,1,0,0};
    
15. int dy[4]={0,0,-1,1};
    
16. int main()
    
17. {
    
18.     cin>>r>>c;
    
19.     for(int i=1;i<=r;i++)
    
20.         for(int j=1;j<=c;j++)
    
21.         {
    
22.             cin>>f[(i-1)*c+j].h;
    
23.             l[i][j]=1;
    
24.             h[i][j]=f[(i-1)*c+j].h;
    
25.             f[(i-1)*c+j].x=i;
    
26.             f[(i-1)*c+j].y=j;
    
27.         }
    
28.     for(int i=1;i<=r;i++)h[i][0]=h[i][c+1]=-1;
    
29.     for(int j=1;j<=c;j++)h[0][j]=h[r+1][j]=-1;
    
30.     sort(f+1,f+r*c+1);
    
31.     for(int i=1;i<=r*c;i++)
    
32.         for(int j=0;j<4;j++)
    
33.         if(h[f[i].x][f[i].y]>h[f[i].x+dx[j]][f[i].y+dy[j]]&&h[f[i].x+dx[j]][f[i].y+dy[j]]!=-1)
    
34.             l[f[i].x+dx[j]][f[i].y+dy[j]]=max(l[f[i].x+dx[j]][f[i].y+dy[j]],l[f[i].x][f[i].y]+1);
    
35.     for(int i=1;i<=r;i++)
    
36.         for(int j=1;j<=c;j++)len=max(len,l[i][j]);
    
37.     cout<<len;
    
38.     return 0;
    
39. }
    

复制代码

admin

两种做法，一个是类似导弹飞机那样的最长不下降序列的做法，一个是记忆化搜索，两个都要认真体会

秀木于林

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int dr[4]={-1,0,1,0};
   
4. int dc[4]={0,-1,0,1};
   
5. int x,y,a[110][110],f[110][110],ans;
   
6. bool isplace(int i,int j)
   
7. {
   
8.     return (i>=1 && i<=x && j>=1 && j<=y);
   
9. }
   
10. int dfs(int r,int c)
    
11. {
    
12.     int tr=0,tc=0,mh=1,h=0;
    
13.     if(f[r][c]>-1) return f[r][c];
    
14.     else for(int i=0;i<=3;i++)
    
15.     {
    
16.         tr=r+dr[i],tc=c+dc[i];
    
17.         if(isplace(tr,tc) && a[r][c]>a[tr][tc]) {h=max(f[tr][tc],dfs(tr,tc)+1);if(h>mh) mh=h;}
    
18.     }
    
19.     return f[r][c]=mh;
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>x>>y;
    
24.     for(int i=1;i<=x;i++)
    
25.         for(int j=1;j<=y;j++)
    
26.     {cin>>a[i][j];f[i][j]=-1;}
    
27.     for(int r=1;r<=x;r++)
    
28.         for(int c=1;c<=y;c++)
    
29.     {
    
30.     if(dfs(r,c)>ans) ans=dfs(r,c);
    
31.     }
    
32.     cout<<ans;
    
33.     return 0;
    
34. }
    

复制代码