题意：第一行输入n和c,表示有n层楼，电梯来到需要时间c
输入两行数，每行n-1个，表示从一楼到二楼，二楼到三楼.....n-1楼到n楼，a[ ] 走楼梯和 b[ ] 乘电梯花费的时间
思路：动态规划，考虑几种状态，假设当前在i-1层，想要去i层，有两种方法，乘电梯，走楼梯。
i-1层要考虑由什么状态到i-1层的，电梯和楼梯，如果是电梯，走楼梯或者乘电梯直接加上需要的时间即可，如果是楼梯状态，继续走楼梯加上a[ i ]即可，如果要坐电梯，加上电梯花费时间的同时也要加上等待电梯的时间；
此时列出动态转移方程,假设楼梯状态是0,电梯状态是 1
dp[ i ][ 0 ]=max{ dp[ i-1 ][ 0 ]+a[ i ] ,dp[ i-1 ][ 1 ]+ b[ i ] +c};
dp[ i ][ 1 ]=max{dp[ i-1 ][ 0 ] +a[ i ] ,dp[ i-1 ][ 1 ] +b[ i ]};
注意：当第一次坐电梯时，一定加上c
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define N 200005 int n,c,a[N],b[N],dp[N][2]; int main() { while(~scanf("%d%d",&n,&c)) { for(int i=1;i<n;i++) scanf("%d",&a[i]);//楼梯 for(int j=1;j<n;j++) scanf("%d",&b[j]);//电梯 memset(dp,0,sizeof(dp)); /* 状态转移方程 [i]当前楼层 [j]怎么来的 [k]怎么走的 0 楼梯 1电梯*/ /*dp[i][0][0]=min(dp[i-1][0][0]+a[i],dp[i-1][1][0]+a[i]); dp[i][0][1]=min(dp[i-1][0][0]+a[i],dp[i-1][1][0]+a[i]); dp[i][1][0]=min(dp[i-1][0][1]+b[i]+c,dp[i-1][1][1]+b[i]); dp[i][1][1]=min(dp[i-1][0][1]+b[i]+c,dp[i-1][1][1]+b[i]);*/ int w=0; for(int i=1;i<n;i++) { dp[i][0]=min(dp[i-1][0]+a[i],dp[i-1][1]+a[i]); if(i==1) w=c; else w=0;//第一次乘电梯必须加上c dp[i][1]=min(dp[i-1][0]+b[i]+c,dp[i-1][1]+b[i]+w); } for(int i=0;i<n-1;i++) printf("%d ",min(dp[i][0],dp[i][1])); printf("%d\n",min(dp[n-1][0],dp[n-1][1])); } return 0; }
