Minimum sum subsequence such that at least one of every four consecutive elements is picked | CPP program to calculate minimum possible sum for given constraint ; function to calculate min sum using dp ; if elements are less than or equal to 4 ; save start four element as it is ; compute sum [ ] for all rest elements ; sum [ i ] = ar [ i ] + ( * min_element ( sum + i - 4 , sum + i ) ) ; ; Since one of the last 4 elements must be present ; driver program
#include <bits/stdc++.h> NEW_LINE typedef long long ll ; using namespace std ; int minSum ( int ar [ ] , int n ) { if ( n <= 4 ) return * min_element ( ar , ar + n ) ; int sum [ n ] ; sum [ 0 ] = ar [ 0 ] ; sum [ 1 ] = ar [ 1 ] ; sum [ 2 ] = ar [ 2 ] ; sum [ 3 ] = ar [ 3 ] ; for ( int i = 4 ; i < n ; i ++ ) sum [ i ] = ar [ i ] + ( * min_element ( sum + i - 4 , sum + i ) ) ; return * min_element ( sum + n - 4 , sum + n ) ; } int main ( ) { int ar [ ] = { 2 , 4 , 1 , 5 , 2 , 3 , 6 , 1 , 2 , 4 } ; int n = sizeof ( ar ) / sizeof ( ar [ 0 ] ) ; cout << " Minimum ▁ sum ▁ = ▁ " << minSum ( ar , n ) ; return 0 ; }