60分求助
查看原帖
60分求助
116495
GMU_QinYuCheng楼主2022/6/2 22:09

想着从前往后做一遍最长上升,再求一遍最长下降。 为什么错啊 !

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int h[N];
int up[N], down[N];//求最长上升子序列和最长下降子序列 
int n;
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> h[i];
	//求最长上升子序列 
	for(int i = 1; i <= n; i ++)
	{
		up[i] = 1;
		for(int j = 1; j < i; j ++)
		{
			if(h[j] < h[i]) up[i] = max(up[i], up[j] + 1);
			//if(h[j] > h[i]) down[i] = max(down[i], down[j] + 1);
		}	
	} 
	//求最长下降子序列 
	for(int i = 1; i <= n; i ++)
	{
		 down[i] = 1;
		for(int j = 1; j < i; j ++)
		{
		//	if(h[j] < h[i]) up[i] = max(up[i], up[j] + 1);
			if(h[j] > h[i]) down[i] = max(down[i], down[j] + 1);
		}	
	}
	int res = 0;
	for(int i = 1; i <= n; i ++) res = max(res, up[i] + down[i] - 1);
	cout << n - res << endl;
	return 0;
}
2022/6/2 22:09
加载中...