返回题解分享
讨论 / 题解分享/ 帖子详情

蜗牛(编程题) - 题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

double dp[100010][2];//dp数组记录用时
double arr[100010];//arr记录柱子x轴坐标
ll a[100010];//a记录起点
ll b[100010];//b记录终点
ll n;//柱子的数量

int main(){
    //输入数据
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>arr[i];
    }
    for(int i = 1; i < n; i++){
        cin>>a[i]>>b[i+1];
    }
    b[1] = 0; a[n] = 0;
    //初始化dp
    dp[1][0] = arr[1];
    dp[1][1] = arr[1];
    //填表
    for(int i = 2; i <= n; i++){
        //去第i个柱子走传送门
        double dis = b[i-1] > a[i-1] ? (b[i-1]-a[i-1])/1.3 : (a[i-1]-b[i-1])/0.7;
        dp[i][1] = min(dp[i-1][0] + a[i-1]/0.7 ,
                       dp[i-1][1] + dis);

        //去第i个柱子不走传送门
        dp[i][0] = min(dp[i-1][0] + arr[i] - arr[i-1] ,
                       dp[i-1][1] + arr[i] - arr[i-1] + b[i-1]/1.3);
        
        //如果走传送门到终点,那就还要往下爬
        if(i == n) dp[i][1] += b[i]/1.3;    

        //cout<<dp[i][0]<<' '<<dp[i][1]<<endl;
    }
    double ans = min(dp[n][1], dp[n][0]);
    ans = round(ans*100)/100;
    printf("%.2f",ans);
}
1 回复 0 转发 0 喜欢 7 阅读
回复 (1)
默认 最新
露米 20 小时前
很清晰的 DP 题解,谢谢你的分享。

把到达柱子底端和到达传送门起点作为两个状态来拆解,确实让原本复杂的移动过程变得好理解了。你在处理向上爬(0.7)和向下爬(1.3)的速度差异时,逻辑也考虑得很周全。

对于正在学习动态规划的小伙伴来说,理解 dp[i][1] 的转移逻辑(尤其是不同位置关系的判断)可能是个很好的练习点。如果能稍微补充一下 dis 变量在不同情况下的物理含义,大家读起来可能会更轻松一些。

期待看到你更多的解题心得。
0