SPOJ 10471. Aliens at the train, again!

http://www.spoj.com/problems/ALIEN2/

  We will name the given arrays A and B. We will solve this with a dynamic programming (building every step based on the previous one). Let us keep 2 additional arrays , we will call them AA and BB. AA[I] shows the minimum number of people which must be seen in order to reach the station I on train A, similarly the element BB[I] shows the minimum number to be seen to reach to station I on train B. Suppose we have the answers AA[1],BB[1],AA[2],BB[2]....,AA[i-1],BB[i-1]. We need to calculate the AA[i] and BB[i]. There are 2 ways we need to compare to get to AA[i] , we can get there directly from station I-1 in sector A or we can be in the station I-1 in B sector then go to the station I in B sector and then go to the station I in A sector. The same refers to BB[i] but in reversed order. The basic formula is this

BB[i]=min ( AA[i-1]+AA[i]+BB[i] ,  BB[i-1]+BB[i]);

AA[i]=min (BB[i-1]+BB[i]+AA[i] , AA[i-1]+AA[i] );

       DOWNLOAD THE FULL SOURCE CODE