首页 > 试题广场 >

合唱队

[编程题]合唱队
  • 热度指数:335899 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
\hspace{15pt}音乐课上,老师将 n 位同学排成一排。老师希望在不改变同学相对位置的前提下,从队伍中选出最少数量的同学,使得剩下的同学排成合唱队形。
\hspace{15pt}记合唱队形中一共有 k 位同学,记编号为 1,2,\dots,k ,第 i 个人的身高为 h_i 。要求:存在一位同学编号为 i \left(1 < i < k\right) ,使得 h_1,h_2,\dots,h_{i-1} 严格递增,且 h_{i+1},h_{i+2},\dots,h_k 严格递减;更具体地,合唱队形呈 h_1 < h_2 < \cdots < h_{i-1} < h_ih_i > h_{i+1} > \cdots > h_k
\hspace{15pt}你能帮助老师计算,最少需要出列多少位同学,才能使得剩下的同学排成合唱队形?

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 3000\right) 代表同学数量。
\hspace{15pt}第二行输入 n 个整数 h_1,h_2,\dots,h_n \left(0 \leqq h_i \leqq 10^5\right) 代表每一位同学的身高。


输出描述:
\hspace{15pt}输出一个整数,代表最少需要出列的同学数量。
示例1

输入

8
186 186 150 200 160 130 197 200

输出

4

说明

\hspace{15pt}在这个样例中,有且仅有两种出列方式,剩下的同学分别为 \{186, 200, 160, 130\}\{150, 200, 160, 130\}
#include <stdio.h>

#define max(a,b)   ( (a)>(b)?(a):(b) )

int main() {
    int i,j,num=0;
    int max=0;
    while (scanf("%d", &num) != EOF) { // 注意 while 处理多个 case

        int arr[num];
        int left[num];
        int right[num];
        int result[num];

        for (i=0;i<num;i++)
            scanf("%d", &arr[i]);

        //计算节点i的最大左递增子序列,存放于left[i]
        for (i=0;i<num;i++){
            left[i]=1;  //初始化每一个节点的左递增子序列为1 <=> 当前节点自己
            for (j=0;j<i;j++){
                if (arr[j]< arr[i])   //i左边发现一个节点j
                    left[i] = max(left[j]+1, left[i]);  //动态规划,取左边所有left[j]+1的最大值,作为left[i]。
            }
        }
        //计算节点i的最大右递减子序列,存放于right[i]
        for (i=num-1;i>=0;i--){
            right[i]=1; //初始化每一个节点的右递减子序列为1 <=> 当前节点自己
            for(j=num-1;j>i;j--){
                if (arr[i]>arr[j])  //i右边发现一个节点j
                    right[i] = max(right[j]+1, right[i]);

            }
        }
        //合并取的当前节点i的最大队形数目
        for(i=0;i<num;i++)
            result[i] = left[i]+right[i]-1; //当前节点i在left和right重复计数,需-1

        //找出全节点的最大值
        for(i=0;i<num;i++)
            max = max(result[i], max);

        printf("%d", num - max);    //剔除的节点数

    }
    return 0;
}
发表于 2024-06-17 15:25:05 回复(0)
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

void GetIncreaseLen(int dp_increase[], int num[], int len)
{
    dp_increase[0] = 1;
    for(int i = 1; i < len; i++){
        dp_increase[i] = 1;
        for(int j = 0; j < i; j++){
            if(num[i] > num[j]){
                int temp = dp_increase[j] + 1;
                dp_increase[i] = max(temp, dp_increase[i]);
            }
        }
    }

}

void GetDecreaseLen(int dp_decrease[], int num[], int len)
{
    dp_decrease[len-1] = 1;
    for(int i = len-2; i >= 0; i--){
        dp_decrease[i] = 1;
        for(int j = len-1; j > i; j--){
            if(num[i] > num[j]){
                int temp = dp_decrease[j] + 1;
                dp_decrease[i] = max(temp, dp_decrease[i]);
            }
        }
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    int num[n];
    for(int i = 0; i < n; i++){
        scanf("%d", &num[i]);
    }
    int res = 0;
    if(n == 1){
        res = 0;
    }else if(n == 2){
        res = 1;
    }else{
        int dp_increse[n];
        int dp_decrese[n];
        int maxLen = 1;
        GetIncreaseLen(dp_increse, num, n);
        GetDecreaseLen(dp_decrese, num, n);
        for(int i = 0; i < n; i++){
            if(dp_increse[i] == 1 || dp_decrese[i] == 1){
                continue;
            }
            maxLen = max(maxLen, (dp_decrese[i]+dp_increse[i]-1));
        }
        res = n - maxLen;
    }
    printf("%d\n", res);
    return 0;
}

发表于 2023-11-15 22:19:05 回复(0)
#include <stdio.h>
#include <stdlib.h>

void search(int* hight, int* top, int* len) {
    static int sta[1500] = {};
    for (int x = *top; x >= 0; x--)
        if (*hight > sta[x] || !(*hight | sta[x])) {
            sta[x + 1] = *hight;
            *len += x;
            *top += x == *top ? 1 : 0;
            break;
        }
}

int main() {
    int n, top = 0, maxnum = 0;
    scanf("%d", &n);
    int len[3000]={}, arr[n];

    for (int i = 0; i < n; i++) {   //求左端不下降子序列长度
        scanf("%d", arr + i);
        search(arr + i, &top, len + i);
    }
    top = 0;
    for (int i = n - 1; i >= 0; i--) {  //求右端不下降子序列长度
        search(arr + i, &top, len + i);
        if (len[i] + 1 > maxnum)
            maxnum = len[i] + 1;
    }
    printf("%d\n", n - maxnum); //输出结果
}

发表于 2023-03-21 11:33:00 回复(1)
#include <stdio.h>
#include <string.h>

#define MAXN 3000

static int N;
static int tall[MAXN];
static int dpl[MAXN], dpr[MAXN];

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &tall[i]);
    }
    
    for (int i = N - 1; i >= 0; i--) {
        for (int j = N - 1; j > i; j--) {
            dpr[i] = tall[j] < tall[i] ? max(dpr[i], dpr[j] + 1) : dpr[i];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            dpl[i] = tall[j] < tall[i] ? max(dpl[i], dpl[j] + 1) : dpl[i];
        }
    }

    int resK = 0;
    for (int i = 0; i < N; i++)
        resK = max(resK, dpr[i] + dpl[i] + 1);

    printf("%d", N - resK);
    return 0;
}

发表于 2023-02-27 17:03:17 回复(0)
#include <stdio.h>
#include <stdlib.h>

int inc_dp[3072];//最大递增序列
int dec_dp[3072];//最小递增序列
int max(int a,int b)
{
    return (a>b?a:b);
}
int main(void)
{
    int n;
    int h[3072];
    int i = 0,j=0;
    int fo_num = 0;
    int dp_max= 0;
    while(scanf("%d",&n)!= EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&h[i]);
            inc_dp[i]=dec_dp[i] = 1;//包括自己至少有一个
        }
        for(i=1;i<n;i++)
        {
            for(j=i-1;j>=0;j--)
            {
                if(h[i]>h[j] && inc_dp[i] < (inc_dp[j]+1) )
                {
                     inc_dp[i]= (inc_dp[j]+1);
                }
            }            
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=i+1;j<n;j++)
            {
                if(h[i]>h[j] && dec_dp[i] < (dec_dp[j]+1))
                {
                     dec_dp[i] = (dec_dp[j]+1);
                }
            }            
        }
        for(i = 0;i<n;i++)
        {
           dp_max = max(dp_max,inc_dp[i]+dec_dp[i] -1); 
        }
        fo_num = n-dp_max;
        printf("%d\n",fo_num);
    }
    return 0;
}

发表于 2022-07-01 09:06:43 回复(0)
  1. 动态规划:时间复杂度O(n^2)
    #include <stdio.h>
    #include <string.h>
    
    int main(){
        int N;scanf("%d",&N);
        int a[N];int max;
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
        }
        //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数
        int dp_r[N];memset(dp_r,0,sizeof(dp_r));
        for(int i=N-2;i>-1;i--){
            max=-1;
            for(int j=i+1;j<N;j++){
                if(a[i]>a[j] && dp_r[j]>max){
                    max=dp_r[j];
                    dp_r[i]=dp_r[j]+1;
                }
            }
        }
        //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数
        int dp_l[N];memset(dp_l,0,sizeof(dp_l));
        for(int i=1;i<N;i++){
            max=-1;
            for(int j=i-1;j>-1;j--){
                if(a[i]>a[j] && dp_l[j]>max){
                    max=dp_l[j];
                    dp_l[i]=dp_l[j]+1;
                }
            }
        }
        //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值
        for(int i=0;i<N;i++){
            if(dp_r[i]+dp_l[i]>max){
                max=dp_r[i]+dp_l[i];
            }
        }
        printf("%d",N-max-1);
    }
  2. 建立辅助数组,维持辅助数组元素有序排列,用二分查找找到原数组元素在该辅助数组中该插入的位置,该位置即为动态规划中dp[i]的值,时间复杂度O(nlogn)
    #include <stdio.h>
    #include <string.h>
    
    int search(int* a,int key,int high){//二分查找
        int low=0,mid;
        while(low<=high){
            mid=(low+high)/2;
            if(a[mid]==key){
                return mid;
            }
            else if(a[mid]>key){
                high=mid-1;
            }
            else{
                low=mid+1;
            }
        }
        if(a[mid]>key){
            return mid;
        }
        else{
            return mid+1;
        }
    }
    
    int main(){
        int N;scanf("%d",&N);
        int a[N];int b[N];memset(b,0,sizeof(b));//辅助数组
        for(int i=0;i<N;i++){
            scanf("%d",&a[i]);
        }
        int max=0;int p;
        //顺序遍历,以当前元素为基准,记录其左边的最大严格递增序列的元素个数
        int dp_l[N];dp_l[0]=0;
        b[max]=b[0]=a[0];
        for(int i=1;i<N;i++){
            if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
                dp_l[i]=0;
                b[0]=a[i];
            }
            else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界
                dp_l[i]=++max;
                b[max]=a[i];
            }
            else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
                p=search(b,a[i],max);
                dp_l[i]=p;
                b[p]=a[i];
            }
        }
        max=0;
        //逆序遍历,以当前元素为基准,记录其右边的最大严格递减序列的元素个数
        int dp_r[N];dp_r[N-1]=0;memset(b,0,sizeof(b));
        b[max]=b[0]=a[N-1];
        for(int i=N-2;i>-1;i--){
            if(a[i]<=b[0]){//原数组元素值超过辅助数组下界就替换
                dp_r[i]=0;
                b[0]=a[i];
            }
            else if(a[i]>b[max]){//原数组元素值超过辅助数组上界,将其插入后形成新的上界
                dp_r[i]=++max;
                b[max]=a[i];
            }
            else{//原数组元素值在中间就在辅助数组中查找刚好大于它的数并替换
                p=search(b,a[i],max);
                dp_r[i]=p;
                b[p]=a[i];
            }
        }    
        //遍历整个数组,计算当前元素dp_r[i]+dp_l[i]的大小,计算最大值
        for(int i=0;i<N;i++){
            if(dp_r[i]+dp_l[i]>max){
                max=dp_r[i]+dp_l[i];
            }
        }
        printf("%d",N-max-1);
    }

发表于 2022-06-08 16:43:53 回复(0)
#include <stdio.h>
#define    N    3000
int main()
{
    int height[N],left[N]={0},right[N]={0},n,i,j,flag,max=0;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&height[i]);
    //从左到右寻找递增子列
    for(i=0;i<n;i++)
    {
        flag=0;
        if(i==0)
            left[i]=1;
        else
        {
            for(j=0;j<i;j++)
            {
                if(height[i]>height[j]&&left[j]+1>left[i])
                {
                    left[i]=left[j]+1;
                    flag=1;
                }
                else if(flag==0)
                    left[i]=1;
            }
        }
    }
    //从右往左寻找递增子列
    for(i=n-1;i>=0;i--)
    {
        flag=0;
        if(i==n-1)
            right[i]=1;
        else
        {
            for(j=n-1;j>i;j--)
            {
                if(height[i]>height[j]&&right[j]+1>right[i])
                {
                    right[i]=right[j]+1;
                    flag=1;
                }
                else if(flag==0)
                    right[i]=1;
            }
        }
    }
    for(i=0;i<n;i++)
        left[i]+=right[i]-1;
    for(i=0;i<n;i++)
        if(left[i]>max)
            max=left[i];
    printf("%d\n",n-max);
    return 0;
}

发表于 2022-04-25 16:54:04 回复(0)
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int num;
    int i,j;
    while(scanf("%d",&num)!=EOF)
    {
        int *qu=(int *)malloc(sizeof(int)*num);
        for(i=0;i<num;i++)
        {
            scanf("%d",&qu[i]);
        }
        int *dp1=(int *)malloc(sizeof(int)*num);
        for(i=0;i<num;i++)
        {
            dp1[i]=1;
            for(j=0;j<i;j++)
            {
                if(qu[j]<qu[i])
                {
                    dp1[i]=dp1[i]>(dp1[j]+1)?dp1[i]:(dp1[j]+1);
                }
            }
        }
        int *dp2=(int *)malloc(sizeof(int)*num);
        for(i=num-1;i>=0;i--)
        {
            dp2[i]=1;
            for(j=num-1;j>i;j--)
            {
                if(qu[j]<qu[i])
                {
                    dp2[i]=dp2[i]>(dp2[j]+1)?dp2[i]:(dp2[j]+1);
                }
            }
        }
        int max=dp1[0]+dp2[0];
        for(i=1;i<num;i++)
        {
            max=max>(dp1[i]+dp2[i])?max:(dp1[i]+dp2[i]);
        }
        printf("%d\n",num-max+1);
    }
    return 0;
}

发表于 2021-07-15 13:41:02 回复(0)