[编程题]合唱队形
- 热度指数：13975 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，
则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入描述:
输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。 第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
输出描述:
可能包括多组测试数据，对于每组数据， 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。
示例1
输入
8 186 186 150 200 160 130 197 220
输出
4
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 101;
int arr[MAXN];
int dp1[MAXN];
int dp2[MAXN];
bool Compare(int a,int b)
{
return a>b;
}
int main()
{
int n;
while(scanf("%d",&n) != EOF)
{
for(int i=0; i<n; ++i)
{
scanf("%d",&arr[i]);
dp1[i] = 1;
dp2[i] = 1;
}
for(int i=0; i<n; ++i)
{
for(int j=0; j<i; ++j)
{
if(arr[j] < arr[i])
{
//dp[i] = dp[j]+1;
dp1[i] = max(dp1[i],dp1[j]+1);
}
}
}
for(int i=n-1; i>=0; --i)
{
for(int j=n-1; j>i; --j)
{
if(arr[j] < arr[i])
{
dp2[i] = max(dp2[i],dp2[j]+1);
}
}
}
int maxAnswer = 0;
for(int i=0; i<n; ++i)
{
int answer = dp1[i] + dp2[i];
maxAnswer = max(maxAnswer,answer);
}
printf("%d\n",n-maxAnswer+1);
}
return 0;
} 正向一次最长递增子序列，反向再做一次，再遍历找到以左右两边最多的节点
发表于 2021-05-11 21:07:17
回复(0)
#include <stdio.h>
int main()
{
int k,i,j,max;
while(scanf("%d",&k)!=EOF)
{
int a[k],b[k],c[k];
for(i=0;i<k;i++)
{
scanf("%d",&a[i]);
b[i]=1;
c[i]=1;
}
for(i=1;i<k;i++)
{
for(j=0;j<i;j++)
{
if(a[i]>a[j])
b[i]=b[i]>b[j]+1?b[i]:b[j]+1;
}
}
for(i=k-2;i>=0;i--)
{
for(j=k-1;j>i;j--)
{
if(a[i]>a[j])
c[i]=c[i]>c[j]+1?c[i]:c[j]+1;
}
}
for(i=0,max=1;i<k;i++)
{
if(b[i]+c[i]>max)
max=b[i]+c[i];
}
printf("%d\n",k-max+1);
}
return 0;
}
发表于 2021-03-27 21:53:55
回复(1)
//前后两次运用LIS(最长递增子序列)
//由于合唱队形是先递增后递减
//a数组是输入序列 b数组是a数组的逆序列
//先对a数组求最长递增子序列
//再对b数组求最长递增子序列
//由于合唱队形最后一人到中间最高的人是一个递增序列
//对应的b数组序列就是从第一位开始求递增序列，这里求递增还是递减要想清楚
//想要出列的人最少，那么留下的人就要最多
//每一个队员对应的LISa值的意思是，假设他自己为最高，则他前面有多少人(包括他自己)
//每一个队员对应的LISb值的意思是，假设他自己为最高，则他后面有多少人(包括他自己)
//所以要找留下的人最多的方法是，依次比较每一个队员对应的LISa和LISb的值的和，最大值即为所求
//求出列人数的方法：总人数减去 （max(LISa+LISb)-1）
//因为LISa和LISb加起来时，最高的那个队员被加了两次
#include<stdio.h>
int main(){
int n;
int a[101],b[101],LISa[101],LISb[101]={0};
int i,j;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++){
scanf("%d",&a[i]);
b[n-i-1]=a[i]; //b数组是a数组的逆序列
}
//a数组求最长递增子序列
LISa[0]=1;
for(i=1;i<n;i++){
int max=0;
for(j=i-1;j>=0;j--){
if(a[j]<a[i]){
if(LISa[j]>max)
max=LISa[j];
}
}
LISa[i]=max+1;
}
//b数组求最长递增子序列
LISb[0]=1;
for(i=1;i<n;i++){
int max=0;
for(j=i-1;j>=0;j--){
if(b[j]<b[i]){
if(LISb[j]>max)
max=LISb[j];
}
}
LISb[i]=max+1;
}
int result=0;
for(i=0;i<n;i++){
if(LISa[i]+LISb[n-i-1]>result){
result=LISa[i]+LISb[n-i-1];
}
}
printf("%d\n",n-result+1); //这里是化简后，把括号去了，所以最后是+1
}
}
发表于 2020-07-29 11:46:27
回复(0)
/*
动态规划：求最长先增后减序列的值
用dp[i]来表示以a[i]为结尾的最长递增子序列的值
用dp2[i]来表示以a[i]为开头的最长递减子序列的值
那么最长先增后减序列的值就是
max(ans,dp[i]+dp2[i]-1); 这里要-1，因为在dp和dp2中，a[i]这个数本身被计算了两次
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int arr[maxn];
int dp[maxn]; // 从左至右最长递增子序列
int dp2[maxn]; // 从右至左最长递减子序列
int main() {
int n;
while(~scanf("%d",&n)) {
for(int i=0; i<n; i++) { // input
scanf("%d",&arr[i]);
dp[i] = 1;
dp2[i] = 1;
}
for(int i=0; i<n; i++) { // 从左到右，求最长递增子序列
for(int j=0; j<i; j++) {
if(arr[j]<arr[i]) {
dp[i] = max(dp[i],dp[j]+1);
}
}
}
for(int i=n-1; i>=0; i--) {
for(int j=n-1; j>i; j--) { // 从右到左，求最长递减子序列
if(arr[j]<arr[i]) {
dp2[i] = max(dp2[j]+1,dp2[i]);
}
}
}
int ans = INT_MAX; // 保存结果
for(int i=0; i<n; i++) {
ans = min(ans,n-dp[i]-dp2[i]+1); // 重复减了自身两次
}
printf("%d\n",ans);
}
}
发表于 2020-03-23 22:42:57
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
// 从左往右升序DP，dp_asc[i]表示i位置为结束的最长递子序列长度
int dp_asc[n];
// 从左往右降序DP, dp_desc[i]表示以i为结尾的最长递减子序列长度
int dp_desc[n];
int std[n];
for (int i = 0; i < n; ++i) {
scanf("%d", &std[i]);
}
// 升序DP dp[i] = max{1, dp[j] + 1 | j < i && std[i] > std[j]}
for (int i = 0; i < n; ++i) {
dp_asc[i] = 1;
for (int j = 0; j < i; ++j) {
if (std[i] > std[j]) {
dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1);
}
}
}
// 降序DP dp[i] = max{1, dp[j] + 1 | j < i && std[i] < std[j]}
// 这里从后往前推，注意if判断
for (int i = n - 1; i >=0 ; --i) {
dp_desc[i] = 1;
for (int j = n - 1; j > i ; --j) {
if (std[i] > std[j]) {
dp_desc[i] = max(dp_desc[i], dp_desc[j] + 1);
}
}
}
int maxN = -1;
// 遍历两个DP
for (int i = 0; i < n; ++i) {
maxN = max(maxN, dp_asc[i] + dp_desc[i] - 1); // 减去重复计算的i
}
cout << n - maxN << endl;
}
return 0;
}
编辑于 2020-03-14 15:33:28
回复(0)
Easy AC! 最大上升子序列的变种。 #include <bits/stdc++.h>
using namespace std;
int main(){
int n,t[110],maxlen[110],rmaxlen[110];
cin>>n;
fill(maxlen,maxlen+n,1);
fill(rmaxlen,rmaxlen+n,0);
for(int i=0;i<n;i++) cin>>t[i];
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(t[j]<t[i]){
maxlen[i]=max(maxlen[i],maxlen[j]+1);
}
}
}
reverse(t,t+n);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(t[j]<t[i]){
rmaxlen[i]=max(rmaxlen[i],rmaxlen[j]+1);
}
}
}
for(int i=0;i<n;i++) maxlen[i]+=rmaxlen[n-i-1];
cout<<(n-*max_element(maxlen,maxlen+n));
return 0;
}
发表于 2020-03-07 20:05:05
回复(1)
两个动态规划，找出左到右递增时最长子序列长度，右到左递增时最长子序列长度。
然后相同下标相加长度相加-1就得到题目要求的队形长度。就可以得到去除的人数
#找出一个方向上的递增子序列长度
def findAscSubString(peopleNum, heightList):
ascSubNum = [1] * peopleNum
for i in range(peopleNum):
if heightList[i] != min(heightList[:i + 1]):
for j in range(i):
if heightList[i] > heightList[j]:
if ascSubNum[i] < ascSubNum[j] + 1:
ascSubNum[i] = ascSubNum[j] + 1
return ascSubNum
#得到去除的队员人数
def findRemovePeople(peopleNum, heightList):
leftPeople = findAscSubString(peopleNum, heightList) #左到右递增
rightPeople = findAscSubString(peopleNum, heightList[::-1]) #右到左递增
rightPeople.reverse() #反转得到下标对应
stayPeople = 0
for i in range(peopleNum):
if stayPeople < leftPeople[i] + rightPeople[i]:
stayPeople = leftPeople[i] + rightPeople[i]
return peopleNum - stayPeople + 1
while True:
try:
peopleNum = int(input())
heightList = list(map(int, input().split()))
print(findRemovePeople(peopleNum, heightList))
except Exception:
break
编辑于 2018-10-01 17:44:44
回复(0)
//数队列，从左到右从小到大，然后从右到左从小到大
#include<stdio.h>
int max(int a,int b){
if(a>b) return a;
else return b;
}
int main(){
int n;
int stu[100];
int left[100],right[100];
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d",&stu[i]);
}
for(int i=0;i<n;i++){
left[i]=1;
right[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(stu[i]>stu[j]){
left[i]=max(left[i],left[j]+1);
}
}
}
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>i;j--){
if(stu[i]>stu[j]){
right[i]=max(right[i],right[j]+1);
}
}
}
int MAX=0;
for(int i=0;i<n;i++){
stu[i]=left[i]+right[i];
MAX=max(MAX,stu[i]);
}
printf("%d\n",n-MAX+1);
}
}
#include<stdio.h>
int max(int a,int b){
if(a>b) return a;
else return b;
}
int main(){
int n;
int stu[100];
int left[100],right[100];
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
scanf("%d",&stu[i]);
}
for(int i=0;i<n;i++){
left[i]=1;
right[i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(stu[i]>stu[j]){
left[i]=max(left[i],left[j]+1);
}
}
}
for(int i=n-2;i>=0;i--){
for(int j=n-1;j>i;j--){
if(stu[i]>stu[j]){
right[i]=max(right[i],right[j]+1);
}
}
}
int MAX=0;
for(int i=0;i<n;i++){
stu[i]=left[i]+right[i];
MAX=max(MAX,stu[i]);
}
printf("%d\n",n-MAX+1);
}
}
发表于 2018-08-22 10:31:03
回复(0)
关键就是找出一个人在从左到右处于第几个位置，从右到左处于第几个位置，然后相加减一就是队列里的人数，找出其中最大的，最少要去除的人数就可以得到了。
#include<stdio.h>
int main(){
int i,j,n,max,ans;
int high[101];
int F1[101],F2[101];
while(scanf("%d",&n)!=EOF){
for(i=1;i<=n;i++)
scanf("%d",&high[i]);
for(i=1;i<=n;i++){
max=1;
for(j=1;j<i;j++)
if(high[i]>high[j]&&F1[j]+1>max)
max=F1[j]+1;
F1[i]=max;
}
for(i=n;i>=1;i--){
max=1;
for(j=n;j>i;j--)
if(high[i]>high[j]&&F2[j]+1>max)
max=F2[j]+1;
F2[i]=max;
}
ans=101;
for(i=1;i<=n;i++){
if(ans>n-(F1[i]+F2[i]-1))
ans=n-(F1[i]+F2[i]-1);
}
printf("%d\n",ans);
}
return 0;
}
发表于 2018-01-29 19:08:25
回复(0)
#include<iostream>
using namespace std;
int dp1[100];//左边升序
int dp2[100];//右边降序
int s[100];
/*
除第一个和最后一个以外，以每个数为中间数。求此数的左边最大升序子序列的长度dp1[i]，以及右边最长降序子序列的长度dp2[i]
最少出列数应为min( n-dp1[i]-dp2[i] )的值
*/
void fun(int n){
int i,j;
//从前到后，求最长升序
for(i=0;i<n;i++){
for(j=i-1;j>=0;j--){
if(s[j]<s[i])
dp1[i]=max(dp1[j]+1,dp1[i]);
}
}
//从后往前，求最长降序
for(i=n-1;i>=0;i--){
for(j=i+1;j<n;j++){
if(s[j]<s[i])
dp2[i]=max(dp2[j]+1,dp2[i]);
}
}
}
int main(){
int n;
while(cin>>n){
int i,j,k;
for(i=0;i<n;i++){
cin>>s[i];
dp1[i]=1;
dp2[i]=1;
}
fun(n);
int min_sum=n-dp1[0]-dp2[0]+1;//重复减了自身两次，故加1
for(k=1;k<n;k++){
if(min_sum>(n-dp1[k]-dp2[k]+1))
min_sum=n-dp1[k]-dp2[k]+1;
}
cout<<min_sum<<endl;
}
return 0;
}
using namespace std;
int dp1[100];//左边升序
int dp2[100];//右边降序
int s[100];
/*
除第一个和最后一个以外，以每个数为中间数。求此数的左边最大升序子序列的长度dp1[i]，以及右边最长降序子序列的长度dp2[i]
最少出列数应为min( n-dp1[i]-dp2[i] )的值
*/
void fun(int n){
int i,j;
//从前到后，求最长升序
for(i=0;i<n;i++){
for(j=i-1;j>=0;j--){
if(s[j]<s[i])
dp1[i]=max(dp1[j]+1,dp1[i]);
}
}
//从后往前，求最长降序
for(i=n-1;i>=0;i--){
for(j=i+1;j<n;j++){
if(s[j]<s[i])
dp2[i]=max(dp2[j]+1,dp2[i]);
}
}
}
int main(){
int n;
while(cin>>n){
int i,j,k;
for(i=0;i<n;i++){
cin>>s[i];
dp1[i]=1;
dp2[i]=1;
}
fun(n);
int min_sum=n-dp1[0]-dp2[0]+1;//重复减了自身两次，故加1
for(k=1;k<n;k++){
if(min_sum>(n-dp1[k]-dp2[k]+1))
min_sum=n-dp1[k]-dp2[k]+1;
}
cout<<min_sum<<endl;
}
return 0;
}
发表于 2019-03-15 12:45:10
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int[] arr = new int[n];
int[] left = new int[n];
int[] right = new int[n];
for(int i=0;i<n;i++){
arr[i] = in.nextInt();
}
//动态规划
//求最长递增子序列
for(int i=0;i<n;i++){
left[i] = 1;
for(int j=i-1;j>=0;j--)
if(arr[j]<arr[i])
left[i] = Math.max(left[i], left[j]+1);
}
//求从右边数起的最长递减子序列
for(int i=n-1;i>=0;i--){
right[i] = 1;
for(int j=i+1;j<n;j++)
if(arr[i]>arr[j])
right[i] = Math.max(right[i], right[j]+1);
}
int max=0;
for(int i=0;i<n;i++){
max = Math.max(max, left[i]+right[i]-1);
}
System.out.println(n-max);
}
}
}
发表于 2018-02-12 18:18:54
回复(0)
#include <bits/stdc++.h>
using namespace std;
int num[100];
int dp1[100];
int dp2[100];
int main(){
int count;
while(cin>>count){
for(int i=0;i<count;i++){
cin>>num[i];
}
for(int i=0;i<count;i++){
dp1[i]=1;
for(int j=0;j<i;j++){
if(num[i]>num[j]){
dp1[i]=max(dp1[j]+1,dp1[i]);
}
}
}
for(int i=count-1;i>=0;i--){
dp2[i]=1;
for(int j=count-1;j>i;j--){
if(num[i]>num[j]){
dp2[i]=max(dp2[i],dp2[j]+1);
}
}
}
int total=0;
for(int i=0;i<count;i++){
total=max(dp1[i]+dp2[i]-1,total);
}
cout<<count-total<<endl;
}
}
枚举每个位置，从左边找最长上升子序列，从右边开始找最长下降子序列，两个数相加就是题目所说的唱歌的人数。
发表于 2020-02-01 21:50:20
回复(0)
/*动态规划的最长子列问题，分别从前往后和从后往前寻找以i点为尾的最长子列，寻找两个子列和的最大值*/
#include<stdio.h>
int main()
{
int N,i,j,max;
while(scanf("%d",&N)!=EOF)
{
int high[200],marka[200],markb[200];
for(i=1;i<=N;i++)
{
scanf("%d",&high[i]);
marka[i]=markb[i]=1; /*每点为尾的子列长度最小都为1*/
}
for(i=2;i<=N;i++) /*从前往后寻找以i点为尾的最长递增子列*/
{
max=marka[i];
for(j=i-1;j>=1;j--)
{
if(high[i]>high[j])
max=(max>marka[j]+1)?max:marka[j]+1;
}
marka[i]=max;
}
for(i=N-1;i>=1;i--) /*从后往前寻找以i点为尾的最长递增子列*/
{
max=markb[i];
for(j=i+1;j<=N;j++)
{
if(high[i]>high[j])
max=(max>markb[j]+1)?max:markb[j]+1;
}
markb[i]=max;
}
max=marka[1]+markb[1]; /*寻找点i两个子列和的最大值*/
for(i=2;i<=N;i++)
max=(max>marka[i]+markb[i])?max:marka[i]+markb[i];
printf("%d\n",N-max+1);
}
return 0;
}
发表于 2017-03-09 10:08:59
回复(1)
/*
* 思路分析
动态规划求出以每个人结尾的左边和右边的最大队列长度
枚举每个人为“中心点”，计算出满足题目要求的队列长度，记录最大值
我们用left[i]表示从左边起到第i个人结束的最长上升队列的人数，那么得到最优解的结构：left[i] =
max{max(left[k] + 1), 1} 0<=k<=i-1 && a[k] < a[i]
同样用right[i]表示从右边起到第i个人结束的最大上升队列的人数，得到：right[i] =
max{max(right[k] + 1), 1} i + 1 <= k <= n - 1 && a[k]
< a[i]
*/
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int cnt = in.nextInt();
int[] height = new int[cnt];
for (int i = 0; i < cnt; i++) {
height[i] = in.nextInt();
}
System.out.println(processChorusFormation(height, cnt));
}
in.close();
}
private static int processChorusFormation(int[] height, int len) {
// TODO Auto-generated method stub
int res = 0;
int[] left = new int[len];
int[] right = new int[len];
left[0] = right[len - 1] = 1;
for (int i = 1; i < len; i++) {
left[i]=1;
for (int k =0; k<i; k++) {
if (height[i] > height[k]) {
left[i] = Math.max(left[i], left[k] + 1);
}
}
}
for (int i = len - 2; i >= 0; i--) {
right[i]=1;
for (int k = len - 1; k > i; k--) {
if (height[i] > height[k]) {
right[i] = Math.max(right[i], right[ k] + 1);
}
}
}
for (int i = 0; i < len; i++) {
if (left[i] + right[i] - 1 > res) {
res = left[i] + right[i] - 1;
}
}
return len-res;
}
}
编辑于 2016-07-29 09:01:22
回复(0)
#include<iostream>
using namespace std;
int dp1[101];
int dp2[101];
int T[101];
int main()
{
int N;
while(cin >> N)
{
for(int i = 0;i < N;i++)
{
cin >> T[i];
}
int maxnum = 0;
for(int i = 0;i < N;i++)
{
dp1[i] = 1;
for(int j = 0;j < i;j++)
{
if(T[i] > T[j])
{
dp1[i] = max(dp1[i],dp1[j] + 1);
}
}
dp2[N - i - 1] = 1;
for(int j = N - 1;j > N - i - 1;j--)
{
if(T[N - i - 1] > T[j])
{
dp2[N - i - 1] = max(dp2[N - i - 1],dp2[j] + 1);
}
}
}
for(int i = 0;i < N;i++)
{
maxnum = max(dp1[i] + dp2[i],maxnum);
}
cout << N - maxnum + 1<< endl;
}
return 0;
}
发表于 2021-02-08 12:21:25
回复(0)
//两次dp求正反序的最长递增子序列长度,这样代码比较简洁高效
#include<iostream>
(720)#include<algorithm>
using namespace std;
const int maxn=105;
int a1[maxn];
int a2[maxn];
int dp1[maxn];//正序以a1[i]为最长递增子序列长度
int dp2[maxn];//逆序以a2[i]为最长递增子序列长度
int main()
{
int n;
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>a1[i];
a2[n-1-i]=a1[i];//逆序
}
for(int i=0;i<n;i++)
{
dp1[i]=1;//初始化为1
dp2[i]=1;
for(int j=0;j<i;j++)
{
if(a1[i]>a1[j])
{
dp1[i]=max(dp1[i],dp1[j]+1);//正序求以a1[i]递增子序列长度
}
if(a2[i]>a2[j])
{
dp2[i]=max(dp2[i],dp2[j]+1);//逆序求以a2[i]递增子序列长度
}
}
}
int ans=0;
for(int i=0;i<n;i++)
{
dp1[i]+=dp2[n-1-i];//相同元素作为末尾的递增子序列长度相加，一个从左到右，一个从右到左
ans=max(ans,dp1[i]);//选出最大的符合要求的长度
}
cout<<n-ans+1<<endl;//两个序列相加时末尾元素计算了两次需要减去1，最终需要出列的人数即n-(ans-1)
}
return 0;
}
发表于 2020-04-07 20:27:31
回复(1)
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
while(cin>>n){
vector<int> t(n);
for(int i=0;i<n;i++){
cin>>t[i];
}
//求以t[i]结尾最长递增子序列长度dp1[i]
vector<int> dp1(n);
dp1[0] = 1;
for(int i=1;i<n;i++){
dp1[i] = 1;
for(int j=0;j<i;j++){
if(t[j]<t[i]) dp1[i] = max(dp1[i],dp1[j]+1);
}
}
//求以t[i]开头的最长递减子序列长度
vector<int> dp2(n);
for(int i=n-1;i>=0;i--){
dp2[i] = 1;
for(int j=i;j<n;j++){
if(t[j]<t[i]) dp2[i] = max(dp2[i],1+dp2[j]);
}
}
//求以上两序列和减一
vector<int> k(n);
for(int i=0;i<n;i++){
k[i] = dp1[i]+dp2[i]-1;
}
cout<<n-*max_element(k.begin(),k.end())<<endl;
}
return 0;
}
发表于 2024-03-29 16:00:41
回复(0)
/* 扩展：排队从低到高、从高到低 */
/* 思路：分别找从左到右最长递增子序列和从右到左最长递增子序列，然后进行操作判断 */
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 101;
int A[MAXN];
int dpL[MAXN];
int dpR[MAXN];
void Init(){
memset(A,0,sizeof(0));
fill(dpL,dpL+MAXN,1);
fill(dpR,dpR+MAXN,1);
}
// 从左、右两个方向更新两个dp
int UpLevel(int n){
// 1.更新左 dpL
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(A[j] < A[i]){
dpL[i] = max(dpL[i],dpL[j]+1);
}
}
}
// 2.更新右 dpR
for(int i=n-1;i>=0;i--){
for(int j=n-1;j>i;j--){
if(A[j] < A[i]){
dpR[i] = max(dpR[i],dpR[j]+1);
}
}
}
// 3.统计
int i=0; // 始终指向 dpL
int j=0; // 始终指向 dpR
int result = 1000000;
while(i<n){
int num = n - (dpL[i]+dpR[j]-1);
result = min(num,result);
i++;
j++;
}
return result;
}
int main(){
int n;
while(cin>>n){
Init();
for(int i=0;i<n;i++){
cin >> A[i];
}
int answer = UpLevel(n);
cout << answer << endl;
}
}
发表于 2023-06-12 16:05:50
回复(0)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Longest Increasing Subsequence
vector<int> LIS(const vector<int>& nums) {
vector<int> res(nums.size(), 1);
for (int i = 0; i < nums.size(); i++)
for (int j = i - 1; j>= 0; j--)
{
if (nums[i] > nums[j])
res[i] = max(res[i], res[j] + 1);
}
return res;
}
vector<int> RELIS(const vector<int>& nums) {
vector<int> res(nums.size(), 1);
for (int i = nums.size() - 1; i >= 0; i--)
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[i] > nums[j])
res[i] = max(res[i], res[j] + 1);
}
return res;
}
int main() {
int N;
while (cin >> N) {
vector<int> nums(N);
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
vector<int> res = LIS(nums);
vector<int> tmp = RELIS(nums);
for (int i = 0; i < N; i++) {
res[i] += tmp[i];
}
cout << N - *max_element(res.begin(), res.end()) + 1 << endl;
}
}
发表于 2023-05-03 22:31:29
回复(0)
#include "stdio.h"
#include "climits"
using namespace std;
int n;//学生人数
int student[110];// 存储学生身高
int leftDP[110];//存储从左到右的最长上升子序列长度
int rightDP[110];//存储从右到左的最长上升子序列长度
void LISDP(){
leftDP[0] = 1;int max = 0;
for (int i = 1; i < n; ++i) {//求leftDP
max = 1;
for (int j = 0; j < i; ++j) {
if(student[j] < student[i]){
if(leftDP[j] + 1 > max)
max = leftDP[j] + 1;
}
}
leftDP[i] = max;
}
rightDP[n-1] = 1;
for (int i = n-2; i >= 0; --i) {
max = 1;
for (int j = n-1; j > i; --j) {
if(student[j] < student[i]){
if(rightDP[j] + 1 > max)
max = rightDP[j] + 1;
}
}
rightDP[i] = max;
}
}
int main(){
while (scanf("%d",&n)!=EOF){
if(n == 2){
printf("0\n");
continue;
}
for (int i = 0; i < n; ++i) {
scanf("%d",student+i);
}
LISDP();
int max = INT_MIN;
for (int i = 0; i < n; ++i) {
if(i == 0){
max = max<rightDP[0]?rightDP[0]:max;
}
if(i == n-1){
max = max<leftDP[n-1]?leftDP[n-1]:max;
}
int temp = leftDP[i] +rightDP[i];
if(max < temp-1)//减1是因为下标为i的同学算了两遍
max = temp-1;
}
printf("%d\n",n-max);
}
}
发表于 2023-03-10 19:10:49
回复(0)
问题信息
难度：
78条回答
236收藏
31101浏览
通过挑战的用户
查看代码-
2023-03-13 16:43:20
-
2023-03-10 12:45:36
-
2023-03-09 16:30:14 -
2023-03-03 16:42:29 -
2023-02-24 10:53:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
