最长递增子序列题目--蓝桥oj742合唱队形（超详细版，思路清晰）

题目链接

依旧，照样例和题目去推出状态转移方程：

我们已知结果是4

正向：

arr[]    186  186  150  200  160  130  197  220

dp1[]     1        1      1     2       2       1     3      4

双重循环，状态转移，如果一个数大于当前值，就将这个数的状态转移到当前值然后加一。

反向：

arr[]   186   186   150   200   160   130   197   220

dp2[]       3     3       2      3       2         1      1        1

反向跟正向同理，循环从最后一个数开始循环即可。

b[i]=dp1[i]+dp2[i]，将正反向相加得到合唱的最大人数

b[]     4   4   3   5   4   2   4    5

最小值是2，最大值是5；

由于正反人数相加是有一个人的人数会重叠相加，所以，我们要在总数减去最大人数时再加一，加上这个已经被减去两次的人。

所以：想要知道最少的出列同学数就是等于n-最大人数+1.

公式也就是这一个

最后，我们根据解题思路就可以写出一整个代码了。

（如此清晰的解题过程，请为我点赞关注谢谢！！）

代码如下：

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio, cin.tie(0), cout.tie(0);
	int n, k, arr[110], dp1[110], dp2[110], sum[110];
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= n; i++) {
		dp1[i] = 1;
		for (int j = 1; j <= i; j++) {
			if (arr[i] > arr[j]) {
				dp1[i] = max(dp1[j] + 1, dp1[i]);
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		dp2[i] = 1;
		for (int j = n; j >= i; j--) {
			if (arr[i] > arr[j]) {
				dp2[i] = max(dp2[j] + 1, dp2[i]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		sum[i] = dp1[i] + dp2[i];
	}
	sort(sum + 1, sum + 1 + n);
	cout << n - sum[n] + 1;
	return 0;
}

这里是红糖，记录我的小白成长史。

如果觉得对你有帮助的话可以点个赞，点个关注，创作不易，请多多支持。

我们下篇文章见!!