题解 | #合唱队# 动态规划

#include #include #include

using namespace std;

int main() { int N; cin >> N;

vector<int> height(N);

for (int i = 0; i < N; i++)
{
	cin >> height[i];
}

vector<int> raise(N);
vector<int> down(N);

raise[0] = 0;
down[N - 1] = 0;

for (int i = 0; i < N; i++)
{
	for (int j = 0; j < i; j++)
	{
		if (height[i] > height[j])
		{
			raise[i] = max((raise[j] + 1), raise[i]);//使用动态规划的方法找到从开头到当前位置，最长的递增序列（不包括第i个元素）
		}
	}
}

for (int m = N-1; m >= 0; m--)
{
	for (int n = N - 1; n > m; n--)
	{
		if (height[n] < height[m])
		{
			down[m] = max((down[n] + 1),down[m]);//使用动态规划的方法找到到当前位置到末尾，最长的递减序列（不包括第i个元素）
		}
	}

}

int g,max=0;
for (int k = 0; k < N; k++)
{
	g = raise[k] + down[k]+1;//求解第i个位置的递增递减序列的和
	max = (g > max) ? g : max;//求解第i个位置，递增递减序列的最长的值是多少
}
cout << (N-max) << endl;//总的人数减去有用的人数就得到了该被提出退伍的人数


return 0;

}