P1434 [SHOI2002]滑雪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题可以用记忆搜索,也可以用dp,这里我就先讲一下dp的写法【本菜鸟学艺不精,只能写一些简单的dp】
首先,如果要想dp的话,先确定集合的含义;
这里定义集合的含义我一般喜欢从状态转移方程出手【这种方法我发现之适用于一些简单的dp】,我们可以推出一个点的状态可以从上下左右4个状态入手,所以就有状态转移方程:
dp[q][p]为dp[i][j]的上下左右四个方向dp值;
因为这个方程只有一个点的信息,所以这个dp状态转移方程的维度只有一个,那就是点的位置;
所以集合的含义我们就可以确定了,dp[i][j]的含义为以[i][j]为终点的轨道的最大长度;
往下接着想就会有另外一个难点,那就是状态转移的时候dp[q][p]可能不是最优解,甚至未曾计算,这里我们就需要对点进行排序了,怎么排呢?
我们可以从低往高计算dp值,这样就不会出现错误了,所以我们就需要以点的高低进行一个排序。
接下来就是具体代码了。
#include<iostream>
#include<vector>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int N=110;
typedef pair<int,int> p;
typedef pair<int,p> two;//p位置,int高度
vector<two> que;
int st[N][N],dp[N][N];//st[i][j]存储[i][j]点的高度
int n,m;//行列
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};//上下左右四个位移变量
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>st[i][j];
two mid; mid.x=st[i][j]; mid.y.x=i,mid.y.y=j;
que.push_back(mid);
}
}
sort(que.begin(),que.end());//排序
int ans=0;
while(que.size()){
int x=que.front().y.x,y=que.front().y.y;
int h=que.front().x;
dp[x][y]=1;
for(int i=0;i<4;i++){//进行状态转移
int x1=x+dx[i],y1=y+dy[i];
if(st[x1][y1]<st[x][y])
dp[x][y]=max(dp[x][y],dp[x1][y1]+1);
}
ans=max(dp[x][y],ans);
que.erase(que.begin());//删除头元素
}
cout<<ans;
}
那么接下来就是记忆搜索了,简单题的记忆搜索的思路一般很简单的;
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=110;
int me[N][N];//记录每个点的最优解
int h[N][N];//记录每个点的高度
int ans;
int n,m;//行列
int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
int dfs(int x,int y){
if(me[x][y]!=1) return me[x][y];//消除重算
for(int i=0;i<4;i++){//遍历上下左右4个方向
int x1=x+dx[i],y1=y+dy[i];
if(h[x][y]>h[x1][y1]&&x1>=0&&x1<n&&y1>=0&&y1<m){
me[x][y]=max(dfs(x1,y1)+1,me[x][y]);//挑选最优解
}
}
return me[x][y];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
cin>>h[i][j],me[i][j]=1;//初始化全部为1
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++ ){
ans=max(ans,dfs(i,j));//dfs返回从[i][j]点出发的最大轨道
}
}
cout<<ans;
}