A93766 正经题解
2025-12-09 19:35:34
发布于:广东
23阅读
0回复
0点赞
题意分析
这是一道经典的线性动态规划问题,每次选择走一步或两步,求到终点的最小代价。
解题思路
我们先要知道,动态规划的根本——子问题该选择什么,即 应该表示什么。先来分析一个最简单的问题:
60
|| 30 35
|| 20 || ||
要跳到任何一块石阶上,青蛙只有两种跳法,从上上块石阶直接跳过来,或者从上一块石阶跳过来。因此我们可以发现,如果可以知道跳到上一块与上上块石阶的最小花费,就可以知道跳到这一块石阶的最小花费。那有没有什么可以确定的条件呢?青蛙不用动就已经在第一块石阶上,因此 为 。青蛙只能从第一块石阶跳到第二块石阶上,因此 为第一、二块石阶的高度差。接下来,根据这些信息就可以得知第三块、第四块、第五块……
AC代码
#include <bits/stdc++.h>
using namespace std;
long long h[100005], dp[100005];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;++i){
cin >> h[i];
}
dp[0] = 1e9+7, dp[1] = 0;
for(int i=2;i<=n;++i){
dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
}
cout << dp[n];
return 0;
}
滚动数组优化
#include <bits/stdc++.h>
using namespace std;
long long h[100005], dp[3];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;++i){
cin >> h[i];
}
dp[0] = 1e9+7, dp[1] = 0;
for(int i=2;i<=n;++i){
dp[2] = min(dp[1]+abs(h[i]-h[i-1]), dp[0]+abs(h[i]-h[i-2]));
dp[0] = dp[1];
dp[1] = dp[2];
}
cout << dp[2];
return 0;
}
时间复杂度
,看到上一篇题解,我也要吐槽下了,橙题都要用 还不抓紧了学,直接复制连思路都不了解下那还打什么竞赛。
全部评论 1
TM的,一道入门题要不是AI代码,要不是我题解的代码,要不是CV



1周前 来自 广东
0还真是,1个AI,5个CV,3个自己写的,吓死了



5天前 来自 广东
0






有帮助,赞一个