text: Minimize the total number of teddies to be distributed | C ++ implementation of the above approach ; Initializing one tablet for each student ; if left adjacent is having higher marks review and change all the dp values assigned before until assigned dp values are found wrong according to given constrains ; if right adjacent is having higher marks add one in dp of left adjacent and assign to right one ; Driver Code ; n number of students ; marks of students ; solution of problem
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; long long fun ( int marks [ ] , int n ) { long long dp [ n ] , temp ; fill ( dp , dp + n , 1 ) ; for ( int i = 0 ; i < n - 1 ; i ++ ) { if ( marks [ i ] > marks [ i + 1 ] ) { temp = i ; while ( true ) { if ( ( marks [ temp ] > marks [ temp + 1 ] ) && temp >= 0 ) { if ( dp [ temp ] > dp [ temp + 1 ] ) { temp -= 1 ; continue ; } else { dp [ temp ] = dp [ temp + 1 ] + 1 ; temp -= 1 ; } } else break ; } } else if ( marks [ i ] < marks [ i + 1 ] ) dp [ i + 1 ] = dp [ i ] + 1 ; } int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += dp [ i ] ; return sum ; } int main ( ) { int n = 6 ; int marks [ 6 ] = { 1 , 4 , 5 , 2 , 2 , 1 } ; cout << fun ( marks , n ) ; return 0 ; }