题解 | #合唱队#
合唱队
https://www.nowcoder.com/practice/6d9d69e3898f45169a441632b325c7b4
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);
}
}
}
