上海计算机学会2023年12月月赛C++乙组T3递增路径
发布时间
阅读量：
阅读量
递增路径
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n×m 个方格组成的方格图，其中第 i 行第 j 列的方格具有高度 hi,j。
请在该方格图中寻找一条递增路径，并输出输出这条递增路径的最大长度。
方格图的路径定义为方格图中一些方格组成的序列，在序列中相邻的方格应在图中共享同一条边。
所谓递增路径，是指从该路径的第一个方格开始，每一个方格的高度都应该严格大于前一个方格。
输入格式
- 第一行：两个整数表示 n 与 m
- 第二行到第 n+1 行：在第 i+1行有 m 个整数表示 hi,1,…,hi,m
输出格式
- 单个整数：表示递增路径的最长长度
数据范围
- 对于 30% 的数据，1≤n,m≤5
- 对于 60% 的数据，1≤n,m≤100
- 对于 100% 的数据，1≤n,m≤500
- 1≤hi,j≤1,000,000
样例数据
输入:
3 3
9 8 7
2 1 6
3 4 5
输出:
9输入:
2 3
7 7 7
7 7 7
输出:
1
解析：
典型的动态规划问题，先将个点按高度从低到高排序，依次确定以其为结尾递增路径的长度（排序是为了保证比他矮的都已经有了结果）。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[505][505];//最长路径长度
int h[505][505];//高度
struct node{//坐标及高度
int x;
int y;
int h;
};
node a[250005];//保存数组
int dx[4]={0,0,1,-1};//四个方向x变化
int dy[4]={1,-1,0,0};//四个方向y变化
int ans=0;
bool cmp(node x,node y){//按高度从低到高排序
return x.h<y.h;
}
int main() {
cin >> n >>m;
int t=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
t++;
a[t].x=i;
a[t].y=j;
a[t].h=x;
h[i][j]=x;
}
}
sort(a+1,a+t+1,cmp);//排序
for(int i=1;i<=t;i++){//逐一计算最长路径
int x=a[i].x;
int y=a[i].y;
dp[x][y]=1;//最低为1
for(int j=0;j<4;j++){//枚举四个方向
int xx=x+dx[j];
int yy=y+dy[j];
if (h[x][y]>h[xx][yy]){//只要比我矮
dp[x][y]=max(dp[x][y],dp[xx][yy]+1);//找最大值
}
}
ans=max(ans,dp[x][y]);//找所有最长路径的最大值
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~