作为洛谷弱狗的第一篇题解,那必须要写的详细一点/doge

还记得初二的时候听老师讲动态规划,完全就没听懂,现在上了高中,再重温动态规划,似乎有了新的感悟。

先说整体做法:优先队列+线性动态规划 42ms

由于x和y的范围在1~100区间,所以直接暴力搜索一定会超时。

一个格子中可以有四个方向分别滑过来:[x+1][y], [x-1][y], [x][y+1],[x][y-1]。先分别判断这四个方位是否比中心的格子低。如果比中心的格子低,那么有如下的动态转移方程:

d[i][j]=max{d[i][j],d[x+1][y]+1,d[x-1][y]+1,d[x][y+1]+1,d[x][y-1]+1}

但是动态规划要考虑无后效性,如果只是挨个遍历,那么结果肯定是错误的。因此要维护一个从小到大的优先队列。从低的点算起,那么对于后续高的点没有影响。

其余请浏览代码注释部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
struct Node{
int x;int y;int h;
};//一个结构体记录这个点的位置和高度

struct cmpl{
bool operator() (const Node a,const Node b) const {
return a.h<b.h;
}
};//优先队列的比较函数

priority_queue<Node,vector<Node>,cmpl> pq;
int d[105][105],a[105][105];
int n,m,i,j;
int main()
{
scanf("%d %d",&n,&m);
int k=0,t;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
cin>>t;
Node q;
q.x=i;q.y=j;q.h=t;
pq.push(q);//将这个元素入队,STL会自动将它从小到大排好
d[i][j]=1;
a[i][j]=t;
}
int maxn=INT_MIN;
while(!pq.empty())
{
Node tmp=pq.top();//依次出队并更新最小值
int ans=1,x1=tmp.x,y1=tmp.y,h1=tmp.h;
if (a[x1+1][y1]>h1) ans=max(ans,d[x1+1][y1]+1);
if (a[x1-1][y1]>h1) ans=max(ans,d[x1-1][y1]+1);
if (a[x1][y1+1]>h1) ans=max(ans,d[x1][y1+1]+1);
if (a[x1][y1-1]>h1) ans=max(ans,d[x1][y1-1]+1);
d[x1][y1]=ans;
maxn=max(maxn,ans);
pq.pop();
}
cout<<maxn<<endl;
return 0;
}