By Elevator or Stairs（动态规划）

原题链接

题意：

一栋楼共n层，从第i层到第i+1层走楼梯和坐电梯需要的时间不同。走楼梯需要的时间为ai，坐电梯存在一个等待时间c（如果从下一层上来靠走的楼梯或者位于第一层），坐电梯也需要bi的时间。问到达第i层需要的最短时间是多少。

思路：

首先应该明确用动态规划的思想来解题，用贪心的话某些情况可能解决不了。比如虽然贪心的情况下，每一步都是选择的最优的情况，但是总体策略可能不是最优。 状态分析：定义上楼的状态和两种方式上楼所需的时间dp[1010][2],a[1010],b[1010]

若去第i层走的楼梯表示为：dp[i][0]

dp[i][0] 取决于 dp[i-1][0]+a[i]（前一层走的楼梯）和dp[i-1][1]+a[i]（前一层做的电梯）的大小

去第i层坐的电梯表示为：dp[i][1]

dp[i][1] 取决于 dp[i-1][0]+b[i]+c(前一层过来走的楼梯) 和dp[i-1][1]+b[i](前一层过来做的电梯）

注意：n层楼，输入数据第二行第三行都是n-1个数据

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int N=2e5+5; int dp[N][2],a[N],b[N];//a走楼梯用时，b坐电梯用时 int main() { int n,c,ans; scanf("%d%d",&n,&c); for(int i=1;i<n;i++) //注意元素个数：1~n-1 scanf("%d",&a[i]); for(int j=1;j<n;j++) scanf("%d",&b[j]); dp[0][0]=0; dp[0][1]=c; //初始等电梯时间 printf("0"); for(int i=1;i<n;i++){ dp[i][0]=min(dp[i-1][0]+a[i],dp[i-1][1]+a[i]); dp[i][1]=min(dp[i-1][0]+b[i]+c,dp[i-1][1]+b[i]); ans=min(dp[i][0],dp[i][1]); printf(" %d",ans); } printf("\n"); return 0; }