题目链接：CodeForces - 1249E
题目大意：你现在所处位置在1楼，给出你两组数据，第一组为从i到i+1走楼梯所需要的时间，第二组为从i到i+1坐电梯所需要的时间，从走楼梯转向电梯需要等c时间。从1楼向二楼走也需要等c时间。
思路：动态规划 。
状态转移方程：
dp[i][0]=min(dp[i-1][0]+b[i-1],dp[i-1][1]+b[i-1]+c);
dp[i][1]=min(dp[i-1][0]+a[i-1],dp[i-1][1]+a[i-1]);
0 代表坐电梯，1为走楼梯，dp[i][j] i为现在所在第几楼，j表示到达 i 现在的位置从 i-1 是走楼梯还是电梯。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int a[200010]; int b[200010]; int dp[200010][5]; int main() { int n,c; while(~scanf("%d%d",&n,&c)) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); for(int i=1; i<=n-1; i++) scanf("%d",&a[i]);//1 for(int i=1; i<=n-1; i++) scanf("%d",&b[i]);//0 //0电，1楼 dp[1][0]=c;//在一楼去二楼的时候使用电梯，需要等c dp[1][1]=0;// for(int i=2;i<=n;i++) { dp[i][0]=min(dp[i-1][0]+b[i-1],dp[i-1][1]+b[i-1]+c); dp[i][1]=min(dp[i-1][0]+a[i-1],dp[i-1][1]+a[i-1]); } printf("0"); int minn; for(int i=2;i<=n;i++) { minn=min(dp[i][0],dp[i][1]); printf(" %d",minn); } printf("\n"); } return 0; }
