题解 | #合唱队#

using System;

using System.Linq;

namespace HJ24

{

    internal class Program

    {

        static void Main(string[] args)

        {

            string strCount = Console.ReadLine();

            int count = int.Parse(strCount);

            string strHeight = Console.ReadLine();

            string[] strHeights = strHeight.Split();

            int[] height = new int[count];

            for (int i = 0; i < height.Length; i++)

            {

                height[i] = int.Parse(strHeights[i]);

            }

            //递增规划

            int[] dpIncre = new int[count];

            //递减规划

            int[] dpDecre = new int[count];

            //双边规划和

            int[] dpSum = new int[count];

            for (int i = 1; i < height.Length; i++)

            {

                //加上自身形成递增数列的数据数目至少为1

                dpIncre[i] = 1;

                for (int j = 0; j < i; j++)

                {

                    if (height[i] > height[j])

                    {

                        //假设之前已经规划过，已经形成了递增数列，

                        //而这次规划的递增数目应该在之前的基础上+1,因为这次身高也是递增

                        int currentIncreCount = dpIncre[j] + 1;

                        //如果这次规划的递增数目大于之前的规划，那么使用这次数目，尽量求最大的递增数目

                        if (currentIncreCount > dpIncre[i])

                        {

                            dpIncre[i] = currentIncreCount;

                        }

                    }

                }

            }

            //反向递增，顺向递减

            for (int i = height.Length - 2; i > 0; i--)

            {

                //加上自身形成递增数列的数据数目至少为1

                dpDecre[i] = 1;

                for (int j = height.Length - 1; j > i; j--)

                {

                    if (height[i] > height[j])

                    {

                        //假设之前已经规划过，已经形成了递减数列，

                        //而这次规划的递减数目应该在之前的基础上+1,因为这次身高也是递减

                        int currentDecreCount = dpDecre[j] + 1;

                        //如果这次规划的递增数目大于之前的规划，那么使用这次数目，尽量求最大的递增数目

                        if (currentDecreCount > dpDecre[i])

                        {

                            dpDecre[i] = currentDecreCount;

                        }

                    }

                }

            }

            for (int i = 0; i < count; i++)

            {

                dpSum[i] = dpIncre[i] + dpDecre[i];

            }

            //自身被规划过两次，因此要减去一次

            int max = dpSum.Max() - 1;

            int outCount = height.Length - max;

            Console.WriteLine(outCount);

        }

    }

}