习题12.3合唱队形(北京大学复试题)

习题12.3合唱队形(北京大学复试题)

合唱队列是升级版的 最大上升子序列问题 + 动态规划法

考虑节点i，节点i左边需要的是最大上升子序列，节点右边是最大下降子序列问题，分别用dp1[i]和dp2[i]来存储

max(dp1[i] + dp2[i] -1) 即为最大的符合条件的队列的人数，用总人数n - (dp1[i] + dp2[i] -1) 即为所求

#include<vector>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	//1. input data
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	//2. 计算i节点的最大上升子序列的长度
	vector<int> dp1(n);
	for (int i = 0; i < n; i++) {
		dp1[i] = 1;
		for (int j = 0; j < i; j++) {
			if (nums[j] < nums[i]) {
				dp1[i] = max(dp1[j] + 1, dp1[i]);
			}
		}
	}
	//3. 计算i节点的最大下降子序列的长度
	vector<int> dp2(n);
	for (int i = n - 1; i >= 0; i--) {
		dp2[i] = 1;
		for (int j = i+1; j < n;j++) {
			if (nums[i] > nums[j]) {
				dp2[i] = max(dp2[i], dp2[j] + 1);
			}
		}
	}
	//4.找到节点i使得dp1[i] + dp2[i] 人数最多，即这样满足要求的人数就越多，出队的人便越少
	int ans = dp1[0] + dp2[0]-1;
	for (int i = 0; i < n; i++) {
		ans = max(ans, dp1[i] + dp2[i] - 1);
	}
	cout << n - ans << endl;
	return 0;
}