text: Minimum score possible for a player by selecting one or two consecutive array elements from given binary array | C ++ program for the above approach ; Stores the minimum score for each states as map < pair < pos , myturn > , ans > ; Function to find the minimum score after choosing element from array ; Return the stored state ; Base Case ; Player A 's turn ; Find the minimum score ; Store the current state ; Return the result ; Player B 's turn ; Find minimum score ; Store the current state ; Return the result ; Function that finds the minimum penality after choosing element from the given binary array ; Starting position of choosing element from array ; 0 denotes player A turn 1 denotes player B turn ; Function Call ; Print the answer for player A and B ; Minimum penalty ; Calculate sum of all arr elements ; Print the minimum score ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; map < pair < int , int > , int > m ; int findMinimum ( int a [ ] , int n , int pos , int myturn ) { if ( m . find ( { pos , myturn } ) != m . end ( ) ) { return m [ { pos , myturn } ] ; } if ( pos >= n ) { return 0 ; } if ( ! myturn ) { int ans = min ( findMinimum ( a , n , pos + 1 , ! myturn ) + a [ pos ] , findMinimum ( a , n , pos + 2 , ! myturn ) + a [ pos ] + a [ pos + 1 ] ) ; m [ { pos , myturn } ] = ans ; return ans ; } if ( myturn ) { int ans = min ( findMinimum ( a , n , pos + 1 , ! myturn ) , findMinimum ( a , n , pos + 2 , ! myturn ) ) ; m [ { pos , myturn } ] = ans ; return ans ; } return 0 ; } int countPenality ( int arr [ ] , int N ) { int pos = 0 ; int turn = 0 ; return findMinimum ( arr , N , pos , turn ) ; } void printAnswer ( int * arr , int N ) { int a = countPenality ( arr , N ) ; int sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; } cout << a ; } int main ( ) { int arr [ ] = { 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printAnswer ( arr , N ) ; return 0 ; }