[SHOI 2002] 滑雪

知识点

动态规划、有向无环图、拓扑顺序

解题思路

按格子高度从低到高排序。dp[u]表示以u为起点的最长下降滑坡，初值1；检查四邻格中比u低的v，用1+dp[v]更新。最终取所有格子的最大值。

正确性说明

严格下降路径不会形成环。处理u时，比u低的邻格已经计算完毕。任意从u出发的非空滑行第一步都到某个更低邻格，故取这些子问题最大值再加1，覆盖且仅覆盖全部下降路径。

易错点

相等高度不能移动；答案是经过的格子数，单格为1；起点可以是任意格子；蛇形长路径使用排序DP避免递归栈限制。

复杂度

令V=RC，时间O(V log V)，空间O(V)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int r,c;cin>>r>>c;int n=r*c;vector<int>h(n),dp(n,1),id(n);for(int&x:h)cin>>x;iota(id.begin(),id.end(),0);sort(id.begin(),id.end(),[&](int a,int b){return h[a]<h[b];});int ans=1;int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};for(int u:id){int x=u/c,y=u%c;for(int k=0;k<4;++k){int xx=x+dx[k],yy=y+dy[k];if(xx>=0&&xx<r&&yy>=0&&yy<c){int v=xx*c+yy;if(h[v]<h[u])dp[u]=max(dp[u],dp[v]+1);}}ans=max(ans,dp[u]);}cout<<ans<<'\n';}