首页 > 代码库 > 合唱队

合唱队

2024-10-24 14:08:39   212人阅读

#include <iostream>
using namespace std;


int main()
{
    int N = 0;
    while(cin>>N)
    {
        int *students = new int [N + 1];//students[0]保留不用
        memset(students, 1, sizeof(int) * (N +1));
        for (int i =1; i <= N; ++i)
        {
            cin>>students[i];
        }
        int *inc1 = new int[N + 1];
        int *inc2 = new int[N + 1];
        memset(inc1, 0 , sizeof(int)*(N+1));
        memset(inc2, 0 , sizeof(int)*(N+1));


        inc1[1] = 1;    
        for (int i = 2; i <= N ; i++)
        {
            inc1[i] = 1;
            for (int j = 1; j < i; j++)
            {
                if (students[i] > students[j] && inc1[j] + 1 > inc1[i])
                {
                    inc1[i] =  inc1[j] + 1;
                }
            }
        }


        inc2[N] = 1;
        for (int i = N - 1; i >= 1; i--)
        {
            inc2[i] = 1;
            for (int j = N; j > i; j--)
            {
                if ((students[i] > students[j]) && (inc2[j]+1 > inc2[i]))
                {
                    inc2[i] = inc2[j]+1;
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= N; i++)
        {
            if (max < inc1[i] +inc2[i] - 1)
            {
                max = inc1[i] +inc2[i] -1;
            }
        }
        cout<<N - max<<endl;
        delete [] students;
    }
    
    return 0;
        
}

合唱队


联系
我们