Submission #4265

#	Time	Username	Problem	Language	Result	Execution time	Memory
4265		dbfud	줄 세우기 (KOI13_jul)	C++98	0 / 22	1000 ms	5576 KiB

jul

#include <iostream>

using namespace std; 

int _lis( int arr[], int n, int *max_ref)
{
    /* Base case */
    if(n == 1)
        return 1;
 
    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]
 
    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If 
       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
       to be updated, then update it */
    for(int i = 1; i < n; i++)
    {
        res = _lis(arr, i, max_ref);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }
 
    // Compare max_ending_here with the overall max. And update the
    // overall max if needed
    if (*max_ref < max_ending_here)
       *max_ref = max_ending_here;
 
    // Return length of LIS ending with arr[n-1]
    return max_ending_here;
}
 
// The wrapper function for _lis()
int lis(int arr[], int n)
{
    // The max variable holds the result
    int max = 1;
 
    // The function _lis() stores its result in max
    _lis( arr, n, &max );
 
    // returns max
    return max;
}

int main()
{
    int numChild = 0 ;
    cin >> numChild ;
    
    int *child = new int[numChild] ; 
     
    for( int i = 0 ; i < numChild ; ++i )
    {
         cin >> child[i] ; 
    }
    
    int MaxLis = lis( child, numChild ) ;
    cout << numChild - MaxLis ; 
    
 
    return 0;
}

• Subtask 1: 0 / 2.2
• Subtask 2: 0 / 3.3
• Subtask 3: 0 / 3.3
• Subtask 4: 0 / 4.4
• Subtask 5: 0 / 4.4
• Subtask 6: 0 / 4.4