华为OJ--合唱队

解题思路

实际上这是一道简单动态规划的题。但是一眼看上去不是很直观。题目所谓的合唱队形就是一个最长上升子序列的拼接。只要求出从队列首到位置 i 的最长上升子序列长度加上从队尾开始到位置 i 的最长上升子序列的长度就能求出合唱队形的总长度。我们还知道总的人数，减一下就能得出要出列的人数了。

求最长上升子序列

现在有一个序列，要求他的最长上升子序列。直观上并不是很好求得，反过来看的话就能比较好理解：
现在对于总序列里的第i个元素来说，包含元素i的最长子序列是多少呢？如果i前面有能构成最长上升序列的（设它为j），而且i数值比j大，那很显然到第i个元素(包含元素i)的最长子序列是到第j个元素的最长子序列+1；否则到第i个元素(包含元素i)的最长子序列就是是1。因为前面没有比他更小的了，只有自身构成一个子序列。

参考代码1

//http://blog.csdn.net/xiaoski/article/details/47161009
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void getLISA(int *pArr, int len, int* pRes); //求最长上升子序列
void getLDSA(int *pArr, int len, int* pRes); //求最长下降子序列---或者说从后往前的上升序列

void main()
{
    int arr[500],Lis[500],Lds[500];
    int len, i, t = 0,index;
    scanf("%d", &len);
    for (i = 0; i < len; i++)
        scanf("%d",&arr[i]);
    getLISA(arr,len,Lis);
    getLDSA(arr, len, Lds);
    for (i = 0; i < len; i++)
        if (t < Lis[i] + Lds[i])
        {
            t = Lis[i] + Lds[i];
            index = i;
        }
    printf("%d\n", len - Lis[index] - Lds[index]+1);
//  system("pause");
}
void getLISA(int *pArr, int len,int *pRes)
{
    int i, j, k;
    for (i = 0; i < len; i++)
    {
        pRes[i] = 1;
        for (j = 0; j < i; j++)
            if (pArr[i]>pArr[j] && pRes[i] < (pRes[j] + 1))
                pRes[i] = pRes[j] + 1;
    }
}
void getLDSA(int *pArr, int len, int *pRes)
{
    int i, j, k;
    for (i = len-1; i >=0; i--)
    {
        pRes[i] = 1;
        for (j = len-1; j >i;j--)
            if (pArr[i]>pArr[j] && pRes[i] < (pRes[j] + 1))
                pRes[i] = pRes[j] + 1;
    }
}

参考代码2

//http://blog.csdn.net/xmh1954/article/details/34422349#
#include <iostream>  
using namespace std;  
  
const int maxn = 100 + 1;  
  
int main()  
{  
    int n;  
    int a[maxn];  
    int f1[maxn];//存放合唱队的人数（从左向右）  
    int f2[maxn];//存放合唱队的人数（从右向左）  
  
    cin>>n;  
    for(int i=1;i<=n;i++)//第0个位置不存放数据，符合平常的思维习惯。  
        cin>>a[i];  
  
    for(int i=1;i<=n;i++)//由左向右依次遍历   
    {     
        f1[i] = 1;//至少有一个人符合条件，就是他自己。所以赋初值1.  
        for(int j=1;j<i;j++)   
        {  
            if(a[i]>a[j]&&f1[i]<f1[j]+1) //f1[i]<f1[j]+1很关键的条件，动态问题  
                f1[i]= f1[j]+1;  
        }          
    }  
  
    for(int i=n;i>=1;i--)//由右向左依次遍历  
    {  
        f2[i] = 1;//至少有一个人符合条件，就是他自己。所以赋初值1.      
        for (int j=i+1;j<=n;j++)   
        {         
            if(a[i]>a[j]&&f2[i]<f2[j]+1)        
                f2[i]=f2[j]+1;    
        }  
    }  
  
    int ans = 0;  
    for(int i=1;i<=n;i++)  
        if(ans<f1[i]+f2[i]-1)   
            ans=f1[i]+f2[i]-1;//最佳解  
    cout<<n-ans<<endl;//需要出列的人数  
    return 0;  
}

参考代码3

//http://blog.csdn.net/lisonglisonglisong/article/details/45241965
#include <iostream>
using namespace std;

int main()
{
    int len;
    cin >> len;
    int *A = new int[len];
    for(int i=0; i<len; ++i)
        cin >> A[i];

    // lis[i]表示以A[i]为结尾的最长递增子序列的长度
    int *lis = new int[len];  
    // lds[i]表示以A[i]为起点的最长递减子序列的长度
    int *lds = new int[len];

    for (int i = 0; i < len; ++i) 
    {
        lis[i] = 1;
        lds[i] = 1;
    }

    for(int i=1; i<len; ++i)
        for(int j=0; j<i; ++j)
            if(A[i] > A[j] && lis[i] < lis[j]+1)
                lis[i] = lis[j] + 1;

    for(int i=len-2; i>=0; --i)
        for(int j=len-1; j>i; --j)
            if(A[i] > A[j] && lds[i] < lds[j]+1)
                lds[i] = lds[j] + 1;

    int maxl = 0;
    for(int i=0; i<len; ++i)
        if(maxl < lis[i]+lds[i])
            maxl = lis[i] + lds[i];

    cout << len - maxl + 1 << endl;

    delete [] lis;
    delete [] lds;
    delete [] A;
    return 0;
}

秒客网

华为OJ--合唱队

相关文章