题解：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

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

题目就这么结束了。

代码实现

CPP

#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

题解：P1434 [SHOI2002] 滑雪

文章操作

算法分析

代码实现

相关推荐

评论

题解：P1434 [SHOI2002] 滑雪