luoguP1434 [SHOI2002]:滑雪

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
#include
#include
#define x first
#define y second
using namespace std;const int N=110;
typedef pair p;
typedef pair two;//p位置，int高度vector 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]

#include
#include
#include
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=0&&y1>n>>m;for(int i=0;i>h[i][j],me[i][j]=1;//初始化全部为1}for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！