合唱队形-题解

目录

1.所需知识点
2.题目分析-转换求LIS和LNIS
3.代码实现

所需知识点

对于这道题你需要明白什么是 最长上升子序列LIS 和 最长不上升子序列LNIS
相关题目：最长上升子序列

题目分析-转换求LIS和LNIS

分析题目，得到重点简化为以下内容：
n个数字，为了满足这n个数字的命题 t_1<...<t_i>t_i+1>...>t_k(1\le i\le k) ，要删去k个数字使其满足命题，求最少删去的数量即k最小
我们得知对于任一元素$t_i$需要它的左边是递增的且以$t_i$为终点，而右边是递减的且以$t_i$为起点
这样我们很容易就发现了！它的对于任一元素$t_i$它左边不就是上升序列，右边不就是下降序列嘛
假设为了满足命题，左边要删去$k_1$个字符而右边要删去$k_2$个字符
要求$k_1$+$k_2$最小
同时$k_1$=左边总数字数-左边的上升序列，$k_2$=右边总数字数-右边的下降序列
那为了$k_1$+$k_2$最小，就得左边的上升序列和右边的下降序列
不就转换成了求$t_i$的LIS和LNIS嘛
所以我们只需要找到LIS+LNIS最大的$t_i$就行了！！！
求得的k只需要n-(LIS+LNIS)+1就行了

代码实现

#include <bits/stdc++.h>
using namespace std;
int n;
int a[105];//身高数组 
int DP_lis[105];//DP数组 存储第i个同学为终点左边的LIS
int DP_lnis[105];//DP数组 存储第i个同学为起点右边的LNIS
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){cin>>a[i];}
	//求以i个同学为终点左边的LIS 
	for(int i=1;i<=n;i++){
		DP_lis[i]=1;
		int before_max=0;
		for(int j=1;j<=i-1;j++){//找到之前可以与当前i数匹配的最优序列 
			if(a[i]>a[j]){before_max=max(before_max,DP_lis[j]);}
		}
		DP_lis[i]=before_max+DP_lis[i];
	}
	//求第i个同学为起点右边的LNIS
	for(int i=n;i>=1;i--){
		DP_lnis[i]=1;
		int before_max=0;
		for(int j=i+1;j<=n;j++){//找到后面可以与当前i数匹配的最优序列 
			if(a[j]<a[i]){before_max=max(before_max,DP_lnis[j]);}
		}
		DP_lnis[i]=before_max+DP_lnis[i];
	}
	//找出lis和lnis最大的i
	int maxn=0;
	for(int i=1;i<=n;i++){
		maxn=max(DP_lis[i]+DP_lnis[i],maxn);
	} 
	cout<<n-maxn+1;//因为maxn是DP_lis[i]+DP_lnis[i]，lnis和lis中包含了两次i同学所以+1 
	return 0;
}