动态规划8--例9.8合唱队形

墨蓝 2023-07-11 15:21 25阅读 0赞

1264：【例9.8】合唱队形  
【题目描述】  
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位同学的身高（厘米）。  
【输出】  
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【算法分析】  
我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。  
如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设

a为身高序列，其中a【i】为同学i的身高；  
b为由左而右身高递增的人数序列，其中b【i】为同学1…同学i间（包括同学i）身高满足递增顺序的最多人数。  
显然b【i】=max\{b【j】| 同学j的身高<同学i的身高\}+1；  
c为由右而左身高递增的人数序列，其中c【i】为同学n…同学i间（包括同学i）身高满足递增顺序的最多人数。  
显然c【i】=max\{C【j】| 同学j的身高<同学i的身高\}+1

由上述状态转移方程可知，  
计算合唱队形的问题具备了最优子结构性质（要使b【i】和c【i】最大，子问题的解b【j】和c【k】必须最大（1<=j<=i-1，i+1<=k<=n））  
和重迭子问题的性质（为求得b【i】和c【i】，必须一一查阅子问题的解b【1】…b【i-1】和c【i+1】…c【n】），  
因此可采用动态程序设计的方法求解。  
显然，合唱队的人数为max\{b【i】+c【i】\}-1（公式中同学i被重复计算，因此减1），n合唱队人数即为解

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    //初始数据
    //a为身高序列,b为由左而右身高递增的人数序列,c为由右而左身高递增的人数序列
    int a[200],b[200],c[200];
    
    //处理函数
    
    //主函数
    int main(){
        //数据初始化
        int n,i,j,maxx;
        //读入学生人数
        cin>>n;
        memset(b,0, sizeof(b));
        memset(c,0, sizeof(c));
        //读入每个学生的身高
        for(i=1;i<=n;i++){
            cin>>a[i];
        }
    
        //事务处理
        //按照从左至右的顺序计算b序列
        for(i=1;i<=n;i++){
            b[i]=1;
            for(j=1;j<=i-1;j++){
                //判断是否可行
                if((a[i]>a[j])&&(b[j]+1>b[i])){
                    b[i]=b[j]+1;
                }
            }
        }
        //按照从右至左的顺序计算c序列
        for(i=n;i>=1;i--){
            c[i]=1;
            for(j=i;j<=n;j++){
                if((a[i]>a[j])&&(c[j]+1>c[i])){
                    c[i]=c[j]+1;
                }
            }
        }
    
    
        //输出数据
        maxx=0;
        //计算合唱队的人数maxx
        for(i=1;i<=n;i++){
            if(b[i]+c[i]>maxx){
                maxx=b[i]+c[i];
            }
        }
        //输出出列人数
        cout<<n-maxx+1<<endl;
    
        return 0;
    }