刚一开始理解错了题意，当我wa了两次之后，重新思考，发现在队列里的士兵可以从左边或者从右边没有比他高的即可。
由此，此题和合唱队形差不多，求一个最长升序列，以及一个最长下降序列，枚举中间的兵和他左边最长下降序列之和。
时间复杂度为o(n^2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;


double a[1010];
int inc[1010],de[1010];


int main(){
    int len;
    while(~scanf("%d",&len))
    {
        for(int i=1;i<=len;i++)
        scanf("%lf",&a[i]);

        memset(inc,0,sizeof(inc));
        memset(de,0,sizeof(de));

        for(int i=1;i<=len;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(inc[i]<=inc[j]&&a[i]>a[j])
                inc[i]=inc[j]+1;
            }
        }
        for(int i=len;i>0;i--)
        {
            for(int j=i+1;j<=len+1;j++)
            {
                if(de[i]<=de[j]&&a[i]>a[j])
                {
                    de[i]=de[j]+1;
                }
            }
        }
        int ans=0,tem;
        for(int i=1;i<=len;i++)
        {
            tem=i;
            for(int j=i+1;j<=len;j++)
            {
                if(de[tem]<=de[j])
                tem=j;
            }
            if(tem==i)
            ans=ans<(de[tem]+inc[i]-1)?(de[tem]+inc[i]-1):ans;
            else
            ans=ans<(de[tem]+inc[i])?(de[tem]+inc[i]):ans;
        }
        printf("%d\n",len-ans);
    }

    return 0;
}

reads比对到参考序列后，bam文件中会有2048、2064这样的flag，表示supplementary alignment 。 为了理解这个概念，可能需要以下知识。



Linear Alignment

An alignment of a read to a single reference sequence that may include insertions, deletions, skips and clipping, but may not include direction changes (i.e. one portion of the alignment on forward strand and another portion of alignment on reverse strand). 1



Chimeric Alignment

An alignment of a read that cannot be represented as a linear alignment. Typically, one of the linear alignments in a chimeric alignment is considered the “representative” alignment, and the others are called “supplementary” and are distinguished by the supplementary alignment flag. 1

Chimeric reads are indicative of structural variation in DNA-seq and it may indicate the presence of chimeric genes in RNA-seq. 2

In short, chimeric reads can be split in to two or more parts, each part would be mapped to reference(it’s not hard-clipped), the total length of the mapped part is longger than read length. 3



Representative alignment

A chimeric alignment that is represented as a set of linear alignments that do not have large overlaps typically has one linear alignment that is considered the representative alignment.

I don’t understand representative alignment with the word “representative” in my mother tongue and could not find more information(figure) about it. One read can align to multiple positions, we can find one alignmnet position which sequence do not have large overlaps, it called representative alighment, for other alignment positions, we called them supplementary alignment.

It seems that GATK can realignment those representative reads to the correctly position via RealignerTargetCreator and IndelRealigner. (WARNING: I am not quite sure if I understand this correctly. If someone could help me, please leave me a message below, thanks, thanks.)



Supplementary Alignment

A chimeric reads but not a representative reads.



Primary Alignment and Secondary Alignment

A read may map ambiguously to multiple locations, e.g. due to repeats. Only one of the multiple read alignments is considered primary, and this decision may be arbitrary. All other alignments have the secondary alignment flag.