题解 P1091 【合唱队形】

羽儇 · 2019-07-23 16:22:30 · 题解

本人第一篇题解

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int f[1000],n,a[1000],sum1,sum2,sum=100000,temp[1000],t,minx;
vector<int>v;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        v.push_back(a[i]);//离散化，我知道T<=230不需要用离散化 
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;//离散化模板 
    for(int i=1;i<=n;i++)//把每个人当做中间的那个，试试，will7101老师讲过的思想，但这是我自己写的代码 
    {
        memset(f,0,sizeof(f));
        memset(temp,0,sizeof(f));//清零 
        t=0;
        for(int j=1;j<=i;j++)
        {
            for(int k=1;k<=j;k++)
                if(a[k]<a[j])f[j]=max(f[j],f[k]);
            f[j]++;
        }
        sum1=f[i];//这是求，从开始的人到中间的 人  的LIS长度 
        memset(f,0,sizeof(f));
        for(int j=i;j<=n;j++)
            temp[++t]=a[n-j+i];//重新组成的一个数组，方便惯性写LIS 
        for(int j=1;j<=t;j++)
        {
            for(int k=1;k<=j;k++)
            {
                if(temp[j]>temp[k])
                f[j]=max(f[j],f[k]);

            }
            f[j]++;
        }
        sum2=f[t];//第二个 数组的LIS 
        minx=n-sum1-sum2+1;//因为我把最中间的那个人，存入了前后两个数组 
        sum=min(sum,minx); 
    }//有毒的LIS 
    cout<<sum;
    return 0;
}//码风奇特，对吧