题目链接：https://vjudge.net/contest/338207#problem/H 翻译： 可以坐电梯或走楼梯从i层走到i+1层。求从底层走到各层所需的最小时间。 如果坐电梯，有个启动时间c，要把启动时间考虑进去。 例如：
10 2 7 6 18 6 16 18 1 17 17 6 9 3 10 9 1 10 1 5到第二层，走楼梯需要7，做电梯需要6，但是有启动时间2，所以从第一层到第二层走楼梯。以此类推。。。。 若到某一层是走楼梯上来的，再到高一层若想坐电梯需要考虑启动时间。 若到某一层是做电梯上来的，再到高一层若继续做电梯，则不需要考虑启动时间。 分析： 考虑动态规划。总共有两种选择，做电梯或走楼梯。 dp[i][0]：表示到第i层是走楼梯到达的。 dp[i][1]：表示到第i层做电梯到达的。 代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2*1e5+10; const int inf=0x3f3f3f3f; int a[N],b[N],dp[N][2]; int n,c; int main() { while(~scanf("%d%d",&n,&c)) { for(int i=1; i<n; i++) scanf("%d",&a[i]); for(int i=1; i<n; i++) scanf("%d",&b[i]); memset(dp,inf,sizeof(dp)); dp[1][0]=0,dp[1][1]=c; //dp[i][0]:走楼梯到达第i层,dp[i][1]:做电梯到达第i层 for(int i=1; i<n; i++) { dp[i+1][0]=min(dp[i+1][0],dp[i][0]+a[i]);/*相邻两层之间的关系*/ dp[i+1][0]=min(dp[i+1][0],dp[i][1]+a[i]); dp[i+1][1]=min(dp[i+1][1],dp[i][0]+b[i]+c); dp[i+1][1]=min(dp[i+1][1],dp[i][1]+b[i]); } for(int i=1; i<=n; i++) printf("%d ",min(dp[i][0],dp[i][1])); printf("\n"); } }