华师一附中OI组

标题: P1434 [SHOI2002]滑雪 [打印本页]

作者: admin 时间: 2018-5-12 23:26
标题: P1434 [SHOI2002]滑雪
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

作者: 吴语林 时间: 2018-7-30 00:01

#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cstdio>
using namespace std;
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;
struct hehe
{
int hei,x,y;
}a[40000];
bool cmp(hehe x,hehe y)
{
return x.hei<y.hei;
}
bool check(int x,int y,int w)
{
if(x<=0||y<=0||x>n||y>m||b[x][y]>=w) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[++jl].hei),a[jl].x=i,a[jl].y=j,b[i][j]=a[jl].hei;
sort(a+1,a+1+jl,cmp);
for(int i=1;i<=jl;i++)
for(int j=0;j<4;j++)
if(check(a[i].x+px[j],a[i].y+py[j],a[i].hei))
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);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
maxn=max(maxn,f[i][j]);
printf("%d",maxn);
return 0;
}

复制代码

作者: 倚窗倾听风吹雨 时间: 2018-8-20 13:47
本帖最后由倚窗倾听风吹雨于 2018-8-20 13:48 编辑

记忆化搜索

#include<iostream>
#include<iomanip>
using namespace std;
const int M=110;
int m,n,a[M][M],dr[4]={0,-1,0,+1},dc[4]={-1,0,+1,0},lens[M][M],ans;
int dfs(int x,int y)
{
if(x<=0 || y<=0 || x>=m+1 || y>=n+1)return 0;
int k=0;
if(lens[x][y]!=1)return lens[x][y];
for(int i=0;i<=3;i++)
if(a[x][y]>a[x+dr[i]][y+dc[i]])
k=max(k,dfs(x+dr[i],y+dc[i])+1);
lens[x][y]=max(lens[x][y],k);
return lens[x][y];
}
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
lens[i][j]=1;
}
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
ans=max(ans,dfs(i,j));
cout<<ans<<endl;
return 0;
}

复制代码

作者: 黄煦喆 时间: 2018-8-30 20:10

#include<iostream>
#include<algorithm>
using namespace std;
int r,c,len=1;
struct ha
{
int h,x,y;
}f[10001];
int l[101][101],h[101][101];
bool operator< (ha p,ha q)
{
return p.h>q.h;
}
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main()
{
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
{
cin>>f[(i-1)*c+j].h;
l[i][j]=1;
h[i][j]=f[(i-1)*c+j].h;
f[(i-1)*c+j].x=i;
f[(i-1)*c+j].y=j;
}
for(int i=1;i<=r;i++)h[i][0]=h[i][c+1]=-1;
for(int j=1;j<=c;j++)h[0][j]=h[r+1][j]=-1;
sort(f+1,f+r*c+1);
for(int i=1;i<=r*c;i++)
for(int j=0;j<4;j++)
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)
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);
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)len=max(len,l[i][j]);
cout<<len;
return 0;
}

复制代码

作者: admin 时间: 2019-10-30 16:37
两种做法，一个是类似导弹飞机那样的最长不下降序列的做法，一个是记忆化搜索，两个都要认真体会

作者: 秀木于林 时间: 2019-11-1 21:01

#include<bits/stdc++.h>
using namespace std;
int dr[4]={-1,0,1,0};
int dc[4]={0,-1,0,1};
int x,y,a[110][110],f[110][110],ans;
bool isplace(int i,int j)
{
return (i>=1 && i<=x && j>=1 && j<=y);
}
int dfs(int r,int c)
{
int tr=0,tc=0,mh=1,h=0;
if(f[r][c]>-1) return f[r][c];
else for(int i=0;i<=3;i++)
{
tr=r+dr[i],tc=c+dc[i];
if(isplace(tr,tc) && a[r][c]>a[tr][tc]) {h=max(f[tr][tc],dfs(tr,tc)+1);if(h>mh) mh=h;}
}
return f[r][c]=mh;
}
int main()
{
cin>>x>>y;
for(int i=1;i<=x;i++)
for(int j=1;j<=y;j++)
{cin>>a[i][j];f[i][j]=-1;}
for(int r=1;r<=x;r++)
for(int c=1;c<=y;c++)
{
if(dfs(r,c)>ans) ans=dfs(r,c);
}
cout<<ans;
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)