「动态规划」变体-题解 | #合唱队形#

求2次「最长公共子序列」

• 思路，参考自：https://blog.nowcoder.net/n/e77f39774db14587bb9377f9ba537dcf?f=comment

#include<bits/stdc++.h>
using namespace std;

int one[105];
int two[105];
int dpPrefix[105];
int dpSuffixReverse[105];


int main()
{
    int n;
    while( ~scanf("%d",&n) )
    {
        for(int i=0; i<n; ++i)
        {
            scanf("%d",&one[i]);
            two[n-1-i]=one[i];
        }

        for(int loop=0; loop<n; ++loop)
        {
            dpPrefix[loop]=1;//表示单独自己成为一个尾巴
            dpSuffixReverse[loop]=1;

            for(int pre=0; pre<loop; ++pre)
            {
                if( one[loop]>one[pre] )
                {
                    dpPrefix[loop]=max( dpPrefix[pre]+1 ,dpPrefix[loop] );
                }

                if( two[loop]>two[pre] )
                {
                    dpSuffixReverse[loop]=max( dpSuffixReverse[pre]+1, dpSuffixReverse[loop] );
                }
            }
        }

        int del=0;
        for(int i=0; i<n; ++i)
        {
            del=max( del, dpPrefix[i]+dpSuffixReverse[n-1-i] );
        }

        printf("%d\n",n-(del-1) );
    }

    return 0;
}