1 条题解
-
0
#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
- 上传者