合唱队形

C 解法, 执行用时: 3ms, 内存消耗: 296KB, 提交时间: 2022-05-09

#include <stdio.h>
#include <string.h>


/*
解题思路：
最少需要几个同学出列可以转换为对多有几位同学在合唱队列：
即：从中间往两边，左边的：从左到右最大递增子序列长度；右边的：从右到左最大递增子序列长度
算法：从左到右求最大递增子序列长度，从右到左求最大递增子序列长度
两个子序列长度对应相加再减去1（中间数值重复计算），可以知道以任何一个节点为中心的合唱队型最大长度reasult
整个合唱队个数为n,n-reasult为需要最少同学出列的人数
*/
int max(int x, int y)
{
    return x>=y?x:y;
}

int main()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0; i<n; i++)
    {
        scanf("%d",&arr[i]);
    }
    int dp[n],rp[n];
    for(int i=0; i<n; i++)
    {
        dp[i] = 1;
        rp[i] = 1;
    }
    
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[i] = max((dp[j]+1),dp[i]);
            }
        }
    }
    
    for(int i=n-2; i>=0; i--)
    {
        for(int j=n-1; j>i; j--)
        {
            if(arr[i] > arr[j])
            {
                rp[i] = max((rp[j]+1),rp[i]);
            }
        }
    }
    
    int reasult = 0;
    for(int i=0; i<n; i++)
    {
        reasult = max((dp[i] + rp[i]) - 1,reasult);
    }
    int num = 0;
    num = n - reasult;
    printf("%d",num);
    
    
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 304KB, 提交时间: 2022-03-06

#include "stdio.h"
int dp1[1010],dp2[1010];
//dp1[i] 以i为终点，左侧最长递增子序列长度
//dp2[i] 以i为终点，右侧最长递减子序列长度
//出列的人数=n-(dp1[i]+dp2[i]-1),求最小值。
int fun(int x,int y){
    return x>y?x:y;
}
int main(){
    int num,high[1010],i,j,res=99999999;
    scanf("%d",&num);
    for(i=0;i<num;i++){
        dp1[i]=1,dp2[i]=1;
        scanf("%d",&high[i]);
    }
    for(i=0;i<num;i++){           //上升子序列
        for(j=0;j<i;j++){
            if(high[i]>high[j])
                dp1[i]=fun(dp1[i], dp1[j]+1);
        }
    }
    for(i=num-1;i>=0;i--){
        for(j=num-1;j>i;j--){
            if(high[i]>high[j])      //下降子序列
                dp2[i]=fun(dp2[i], dp2[j]+1);
        }
    }
    for(i=0;i<num;i++){
        if(res>(num-(dp1[i]+dp2[i]-1)))
            res=num-(dp1[i]+dp2[i]-1);
    }
    printf("%d\n",res);
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 312KB, 提交时间: 2022-06-12

#include <stdio.h>
#include <string.h>
 
 
/*
解题思路：
最少需要几个同学出列可以转换为对多有几位同学在合唱队列：
即：从中间往两边，左边的：从左到右最大递增子序列长度；右边的：从右到左最大递增子序列长度
算法：从左到右求最大递增子序列长度，从右到左求最大递增子序列长度
两个子序列长度对应相加再减去1（中间数值重复计算），可以知道以任何一个节点为中心的合唱队型最大长度reasult
整个合唱队个数为n,n-reasult为需要最少同学出列的人数
*/
int max(int x, int y)
{
    return x>=y?x:y;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0; i<n; i++)
    {
        scanf("%d",&arr[i]);
    }
    int dp[n],rp[n];
    for(int i=0; i<n; i++)
    {
        dp[i] = 1;
        rp[i] = 1;
    }
     
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[i] > arr[j])
            {
                dp[i] = max((dp[j]+1),dp[i]);
            }
        }
    }
     
    for(int i=n-2; i>=0; i--)
    {
        for(int j=n-1; j>i; j--)
        {
            if(arr[i] > arr[j])
            {
                rp[i] = max((rp[j]+1),rp[i]);
            }
        }
    }
     
    int reasult = 0;
    for(int i=0; i<n; i++)
    {
        reasult = max((dp[i] + rp[i]) - 1,reasult);
    }
    int num = 0;
    num = n - reasult;
    printf("%d",num);
     
     
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-02-25

#include<stdio.h>
int max(int a,int b)
{
	if(a>b){
		return a;
	}
	else{
		return b;
	}
}
int main()
{
	int a[1000],dp1[1000],dp2[1000];
	int n,i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	//求最大上升子序列 
	for(i=1;i<=n;i++){
		dp1[i]=1;
		for(j=1;j<i;j++){
			if(a[j]<a[i]){
				dp1[i]=max(dp1[j]+1,dp1[i]);
			}
		}
	}
	//求 下降 
	for(i=n;i>0;i--){
		dp2[i]=1;
		for(j=n;j>i;j--){
			if(a[i]>a[j]){
				dp2[i]=max(dp2[i],dp2[j]+1);
			}
		}
	}
	int res=0;
	for(i=1;i<=n;i++){
		res=max(res,dp1[i]+dp2[i]-1);
	}
	res=n-res;
	printf("%d",res);
	return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-07-21

#include <bits/stdc++.h> // C++万能头文件
using namespace std;
static const auto io_sync_off = [](){ // lambda表达式
    std::ios::sync_with_stdio(false); // 解除与scanf()等函数的同步
    std::cin.tie(nullptr); // 解除cin和cout的绑定
    return nullptr;
}();

int main() {
    int n;
    cin >> n;
    int nums[n];
    vector<int> dp;
    int left[n]; // 每个下标左侧最长上升子序列长度
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        if (dp.empty() || dp.back() < nums[i])
            dp.push_back(nums[i]);
        else
            *lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
        left[i] = dp.size();
    }
    int right[n]; // 每个下标右侧最长下降子序列长度
    dp.clear(); // 即求从右往左最长上升子序列长度
    for (int i = n - 1; i >= 0; --i) {
        if (dp.empty() || dp.back() < nums[i])
            dp.push_back(nums[i]);
        else
            *lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
        right[i] = dp.size();
    }
    int maxlen = 0;
    for (int i = 0; i < n; ++i)
        maxlen = max(maxlen, left[i] + right[i] - 1);
    cout << n - maxlen << "\n";
    return 0;
}

详情