NC16664 合唱队形

\(LIS\)简单变形。

状态表示：

• \(l[i]\)：\(1～i\)的最长上升子序列长度
• \(r[i]\)：\(i～n\)的最长下降子序列长度

注意最后是输出出列的人数=_=。

const int N=110;
int a[N];
int l[N],r[N];
int n;

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        l[i]=1;
        for(int j=1;j<i;j++)
            if(a[i] > a[j])
                l[i]=max(l[i],l[j]+1);
    }

    for(int i=n;i;i--)
    {
        r[i]=1;
        for(int j=i+1;j<=n;j++)
            if(a[i] > a[j])
                r[i]=max(r[i],r[j]+1);
    }

    int res=0;
    for(int i=1;i<=n;i++)
        res=max(res,l[i]+r[i]-1);
    cout<<n-res<<endl;

    //system("pause");
}

内层\(j\)的两种循环方式均可，因为\(r[i+1～n]\)均在外层循环到\(i\)时计算过了。

    for(int i=n;i;i--)
    {
        r[i]=1;
        for(int j=i+1;j<=n;j++)
            if(a[i] > a[j])
                r[i]=max(r[i],r[j]+1);
    }

    for(int i=n;i;i--)
    {
        r[i]=1;
        for(int j=n;j>i;j--)
            if(a[i] > a[j])
                r[i]=max(r[i],r[j]+1);
    }