题解：P1434 [SHOI2002] 滑雪

· · 题解

原题：P1434 。

算法分析

本题具有无后效性：由于滑雪只能从高往低处滑，当前点的最长滑坡长度仅由其四周更高的点决定，而不会影响那些已处理的高点。因此可采用动态规划求解。

定义状态 f_{i,j} 为滑雪滑到 (i,j) 时所能达到的最长滑坡长度。\ 易得状态转移方程：

f_{i,j}=\max\{f_{i-1,j},f_{i+1,j},f_{i,j-1},f_{i,j+1}\}+1

其中只考虑高度严格大于当前点的相邻位置。\ 由于状态转移依赖于更高位置的值，处理顺序必须按海拔高度从高到低进行，以确保计算每个点时，其所有可能转移的来源点都已求解完毕。

题目就这么结束了。

代码实现

#include<cstdio>
int n,m,s[105][105],dp[105][105],ans;
int addx[4]={1,-1,0,0},addy[4]={0,0,-1,1}; // 四个方向的行列坐标偏移量
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&s[i][j]);
    for(int t=1;t<=n*m;t++){ // 总共处理 n*m 个点
        int ti,tj,maxn=-1e9;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!dp[i][j] && s[i][j]>maxn)maxn=s[i][j],ti=i,tj=j; // 每次选择未处理且海拔最高的点进行 DP 计算
        maxn=0;
        for(int i=0;i<4;i++)if(dp[ti+addx[i]][tj+addy[i]]>maxn && s[ti+addx[i]][tj+addy[i]]>s[ti][tj])maxn=dp[ti+addx[i]][tj+addy[i]]; // 从四个相邻方向转移，只考虑更高的点
        dp[ti][tj]=maxn+1; // 当前点的最长滑坡长度
        if(dp[ti][tj]>ans)ans=dp[ti][tj]; //更新答案
    }
    printf("%d",ans);
    return 0;
}

AC 记录：Record