1 条题解

  • 0
    @ 2026-1-27 18:47:19
    #include<bits/stdc++.h>  
    using namespace std;     
    
    int n;                   // [1] n-输入的楼层总数
    int arr[10100];          // [2] arr数组-存储每层楼飞行所需的时间,下标从1到n
    int dp[10010];           // [3] dp数组-动态规划数组,dp[i]表示到达第i层(并完成飞行)的最短时间
    
    int main(){
    	cin>>n;  // [4] 读取楼层总数n
    	for(int i=1;i<=n;i++) cin>>arr[i];  // [5] 读取每层的飞行时间,存入arr数组(i从1开始对应第1层到第n层)
    	
    	/*
    		题目规则:飞船每次可跳跃1/2层(无时间消耗),之后必须飞行1层(消耗对应层的时间),再进行下一次跳跃。
    		目标是到达顶层(第n层的屋顶),可从第n、n-1、n-2层跳跃上来(最后一步无需飞行),因此只需计算到达这三层的最短时间。
    	*/
    	 // 初始化dp数组
        dp[0] = 0;  // [6] dp[0]-起点(楼底,第0层),无需花费时间
        dp[1] = arr[1];  // [7] dp[1]-到达第1层(必须飞行第1层),花费时间为arr[1]
        dp[2] = arr[2];  // [8] dp[2]-到达第2层(必须飞行第2层),花费时间为arr[2]
        dp[3] = arr[3];  // [9] dp[3]-到达第3层(必须飞行第3层),花费时间为arr[3]
        
        // 状态转移:对于第i层(i≥4),到达它的方式是从i-1、i-2、i-3层跳跃过来后飞行第i层
        for(int i = 4; i <= n; i++){
            dp[i] = min(dp[i-1], min(dp[i-2], dp[i-3])) + arr[i];  // [10] 状态转移方程:到达第i层的最短时间 = 到达i-1/i-2/i-3层的最短时间的最小值 + 第i层的飞行时间
        }
        
        // 到达顶层(第n层的屋顶)可以从第n、n-1、n-2层跳跃上来(最后一步无需飞行),因此取这三层的dp值的最小值
        cout << min(dp[n], min(dp[n-1], dp[n-2])) << endl;  // [11] 输出到达顶层的最短时间,即dp[n]、dp[n-1]、dp[n-2]中的最小值
    	return 0;
    }
    
    • 1

    信息

    ID
    1327
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者