毫无疑问这是一道DP（动态规划题）

问题与最长上升（下降）序列有关
解决了最长上升？下降问题之后
面临的主要问题就是怎么选这个中间的人，我们看一看这个数据范围
枚举完全可行啊!!!!!
那么就枚举每个人作为中间的那个人（他也没说对称是吧）

这个中间人需要保证左边是从左往右上升，右边是从左往右下降。
所以找到每个人左边的最长上升子序列，右边的最长下降子序列(他本身一定是结尾)即可

进行两遍操作，先进行一次最长上升子序列，再进行最长下降子序列，uppi【i】存的是选取第i个人当中间人左边的最长上升序列。down【i】存的是选取第i个人当中间人右边的最长下降序列右边最长下降序列(下降子序列其实就是倒着的上升序列)

蒟蒻代码奉上

#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
inline int read()
{
    int f=1,res=0;char ch = getchar();
    while(ch>'9'||ch<'0'){if(ch == '-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+ch-'0',ch=getchar();
    return f*res;
}
int n,uppi[105],down[105],a[105],ans;
int main()
{
    n=read();
    for(int i=1;i<=n;i++)   a[i] = read(),uppi[i] = down[i] = 1;
    for(int i=2;i<=n;i++) for(int j=1;j<i;j++) if(a[j] < a[i] && uppi[j] >= uppi[i]) uppi[i] = uppi[j] + 1;
    for(int i=n;i>=1;i--) for(int j=n;j>i;j--) if(a[j] < a[i] && down[j] >= down[i]) down[i] = down[j] + 1;
    for(int i=1;i<=n;i++)   ans = max( ans , uppi[i] + down[i] - 1 );           
    printf("%d",n-ans);
    return 0;
}

44msQAQ

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

const int maxn = 5000;
int n, a[maxn], up[maxn], down[maxn];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        up[i] = down[i] = 1;
    for (int i = 0; i < n; i++)
        for (int j = i - 1; j >= 0; j--)
            if (a[i] > a[j])
                up[i] = max(up[i], up[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j])
                down[i] = max(down[i], down[j] + 1);
    int result = 0;
    for (int i = 0; i < n; i++)
        result = max(result, up[i] + down[i] - 1);
    cout << n - result << endl;
    return 0;
}

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    int n,a[101],f[101],g[101],ans=0;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        f[i]=g[i]=1;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=i-1;j++)
            if (a[i]>a[j])
                f[i]=max(f[i],f[j]+1);
    for (int i=n;i>=1;i--)
        for (int j=n;j>=i+1;j--)
            if (a[i]>a[j])
                g[i]=max(g[i],g[j]+1);
    for (int i=1;i<=n;i++)
        ans=max(ans,f[i]+g[i]-1);
    printf("%d\n",n-ans);
}

经典dp
那么怎么做呢（废话）
先从左到右看每个人最多比几个人高，用f1记录下来
从右到左也一样,（用f2记录）
那么f1[i]+f2[i]-1就是第i人加上他自己可以形成的队形（注意要减一，因为从右往左时把自己多加了一遍）
选出最大值
用总人数-最多的队形人数（也就是那个最大值）就OK了

#include<bits/stdc++.h>
using namespace std;
int n,a[105],m,f1[105],ans,f2[105];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        m=0;
        for(int j=1;j<i;j++) if(a[i]>a[j]&&f1[j]>m) m=f1[j];
        f1[i]=m+1;
    }
    for(int i=n;i>0;i--)
    {
        m=0;
        for(int j=n;j>i;j--) if(a[i]>a[j]&&f2[j]>m) m=f2[j];
        f2[i]=m+1;
    }
    for(int i=1;i<=n;i++) if(f1[i]+f2[i]>ans) ans=f1[i]+f2[i];
    cout<<n-(ans-1);
}

在这里看效果更佳哦

var
  a,b,c:array[1..100]of longint;
  max,i,j,n:longint;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do
    for j:=1 to i-1 do
      if (a[j]<a[i]) and (b[i]<b[j]+1) then b[i]:=b[j]+1;
  for i:=n downto 1 do
    for j:=i+1 to n do
      if (a[j]<a[i]) and (c[i]<c[j]+1) then c[i]:=c[j]+1;
  for i:=1 to n do
    if max<c[i]+b[i]+1 then max:=c[i]+b[i]+1;
  writeln(n-max);
end.

#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int N,up[105],down[105],a[105],m;
int main(){
    ios::sync_with_stdio(false);
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>a[i];
        up[i] = down[i] = 1;
    }
    for(int i=2;i<=N;i++){
        for(int j=1;j<i;j++){
            if(a[j]<a[i])
                up[i] = max(up[i],up[j]+1);
        }
    }
    for(int i=N-1;i>=1;i--){
        for(int j=N;j>i;j--){
            if(a[j]<a[i])
                down[i] = max(down[i],down[j]+1);
        }
    }
    for(int i=1;i<=N;i++) m = max(m,up[i]+down[i]-1);
    cout<< N-m;
}

#include <iostream>

using namespace std;

int main() {
int f[2][105];
int n;
int height[105];
for (int i = 0; i < 105; i++) {
f[0][i] = 1;
f[1][i] = 1;
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> height[i];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (height[i] > height[j]) {
if (f[0][i] < f[0][j] + 1) f[0][i] = f[0][j] + 1;
}
if (height[i] < height[j]) {
if (f[1][i] < f[0][j] + 1) f[1][i] = f[0][j] + 1;
if (f[1][i] < f[1][j] + 1) f[1][i] = f[1][j] + 1;
}
}
}
int max = 0;
for (int i = 0; i < n; i++) if (max < f[1][i]) max = f[1][i];
for (int i = 0; i < n; i++) if (max < f[0][i]) max = f[0][i];
cout << n - max;
return 0;
}

简单dp
cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int n,f1[110],f2[110],a[110],ans;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
f1[i]=1;
for(int j=1;j<=i;j++)
{
if(a[i]>a[j]&&f1[j]+1>f1[i])f1[i]=f1[j]+1;
}
}
for(int i=n;i>=1;i--)
{
f2[i]=1;
for(int j=n;j>=i;j--)
{
if(a[i]>a[j]&&f2[j]+1>f2[i])f2[i]=f2[j]+1;
}
}
for(int i=1;i<=n;i++)
{
if(f1[i]+f2[i]-1>ans)ans=f1[i]+f2[i]-1;
}
printf("%d\n",n-ans);
return 0;
}
/*8 186 186 150 200 160 130 197 220*/


/*dp*/
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10001],h[10001],f[10001];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        h[i]=f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[i]&&h[j]+1>h[i]) h[i]=h[j]+1;
        }
    }
    int max=-1;
    for(int i=1;i<=n;i++)
    {
        if(h[i]+f[i]-1>max) max=h[i]+f[i]-1;
    }
    printf("%d",n-max);
    return 0;
}

//合唱队形 vijos
#include<iostream>
using namespace std;

#define maxn 101

int dpup[maxn],dpdown[maxn],a[maxn];

int main(){
int i,j,ret,N,k;
cin>>N;
for(i=1;i<=N;i++){
cin>>a[i];
dpup[i]=dpdown[i]=1;
}
ret=1;
for(i=1;i<=N;i++){
for(j=1;j<i;j++){
if(a[j]<a[i]){
dpup[i]=max(dpup[i],dpup[j]+1);
}
}
}

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

for(i=1;i<=N;i++){
ret=max(ret,dpdown[i]+dpup[i]-1);
}

cout<<N-ret<<endl;
return 0;
}

Vijos的数据似乎并没有T1=T2=...=Tn的情况……
O(n^3)算法：
枚举中间的人，然后求两边的最长递增/递减子序列，注意必须保证两边的人都矮于中间的人

#include <cstdio>
#include <algorithm>

using namespace std;

const int maxN = 100 + 5;

int dp[maxN];
int T[maxN];
int N;

void input()
{
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
        scanf("%d", T + i);
}

int try_solve(int mid)
{
    for (int i = 1; i <= N; i++)
        dp[i] = 0;

    int maxL = 0, maxR = 0;
    for (int i = 1; i < mid; i++)
    {
        if (T[i] >= T[mid])
            continue;
        dp[i] = 1;
        for (int j = 1; j < i; j++)
            if (T[j] < T[i])
                dp[i] = max(dp[i], dp[j] + 1);
        maxL = max(maxL, dp[i]);
    }

    for (int i = mid + 1; i <= N; i++)
    {
        if (T[i] >= T[mid])
            continue;
        dp[i] = 1;
        for (int j = mid + 1; j < i; j++)
            if (T[j] > T[i])
                dp[i] = max(dp[i], dp[j] + 1);
        maxR = max(maxR, dp[i]);
    }

    return maxL + maxR + 1;
}

int solve()
{
    int ans = 1;
    for (int i = 1; i <= N; i++)
        ans = max(ans, try_solve(i));
    return N - ans;
}

int main()
{
    input();
    printf("%d\n", solve());
    return 0;
}

O(n^2)算法：
dp[0][x]：以第x个人结尾的最长递增子序列
dp[1][x]：以第x个人结尾，且已经开始递减的最长“合唱队形”
状态转移过程：
dp[0][x]也就是LIS
dp[1][x]分两种情况（设k＜x）：
（1）从dp[0][k]转移，也就是刚开始递减
（2）从dp[1][k]转移

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxN = 105;
const int inf = 0x3f3f3f3f;

int a[maxN];
int n;

void input()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", a + i);
}

int dp[maxN][2];
//0:increasing
//1:decreasing

int solve()
{
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = 1;
        dp[i][1] = -inf;
    }

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

    int opt = 0;
    for(int i = 1; i <= n; i++)
    {
        opt = max(opt, dp[i][1]);
        opt = max(opt, dp[i][0]);
    }

    return n - opt;
}

int main()
{
    input();
    printf("%d", solve());
    return 0;
}

var
n,i,j,k,ans1,ans2,max:longint;
a,f:array[0..10000] of longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n do
begin
ans1:=0;ans2:=0;
for j:=1 to i-1 do
if a[j]<a[i] then begin
f[j]:=1;
for k:=1 to j-1 do
if (a[k]<a[j])and(f[k]+1>f[j]) then f[j]:=f[k]+1;
end;
for j:=1 to i-1 do
if f[j]>ans1 then ans1:=f[j];
for j:=i+1 to n do
if a[j]<a[i] then begin
f[j]:=1;
for k:=i+1 to j-1 do
if (a[k]>a[j])and(a[k]<a[i])and(f[k]+1>f[j]) then f[j]:=f[k]+1;
end;
for j:=i+1 to n do
if f[j]>ans2 then ans2:=f[j];
if ans1+ans2+1>max then max:=ans1+ans2+1;
end;
writeln(n-max);
end.

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
int ans=1;
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int i,j,n;
cin>>n;
int a[n+1],b[n+1],c[n+1];
for (i=1;i<=n;i++) cin>>a[i];
for (i=1;i<=n;i++)
{
b[i]=1;
for (j=1;j<i;j++)
{
if (a[j]<a[i])
{
b[i]=max(b[i],b[j]+1);
}
}
}
for (i=n;i>=1;i--)
{
c[i]=1;
for (j=n;j>i;j--)
{
if (a[j]<a[i])
{
c[i]=max(c[i],c[j]+1);
}
}
}
for (i=1;i<=n;i++)
{
ans=max(ans,c[i]+b[i]-1);
}
cout<<n-ans<<endl;
system("pause");
return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int up[500], down[500];
int n; bool f1,f2;
int a[500];
int ans = 0x7f;
int dp1[500], dp2[500];
int pos,node;
int upp(int r)
{
memset(dp1, 0x7f, sizeof(dp1));
f1 = false;
node = 0;
for (int i=1; i<r; i++){
pos = lower_bound(dp1, dp1+n+1, a[i]) - dp1;
dp1[pos] = a[i];
node = max(node, pos);
}
if (a[r] > dp1[node]) {
f1 = true;
dp1[++node] = a[r];
}
return node+1;
// for (int i=1; i<=n; i++) cout<<dp1[i]<<" "; cout<<endl;
// return upper_bound(dp1, dp1+n+2, 0x7f) - dp1;
}

int downn(int x){
node = 0;
f2 = false;
memset(dp2, 0x7f, sizeof(dp2));
for (int i=n; i>x; i--){
pos = lower_bound(dp2, dp2+n+1, a[i]) - dp2;
dp2[ pos] = a[i];
node = max(node, pos) ;
}
if (a[x] > dp2[node]){
dp2[++node] = a[x];
f2 = true;
}
return node+1;
// return upper_bound(dp2,dp2+n+2, 0x7f) - dp2;
}

int main(){
cin>>n;
for (int i=1; i<=n; i++)
cin>>a[i];
for (int i=2; i<n; i++){
int u = upp(i); int v = downn(i); //i必选
int now = n - u - v;
if (f1 && f2) now++;
// cout<<f1<<f2<<endl;
// cout<<u<<" "<<v<<" "<<now<<endl;
ans = min(ans, now);
}
ans = min (ans, n-upp(n));
ans = min (ans, n-downn(1));
cout<<ans<<endl;
return 0;
}

最长上升+最长下降

#include<bits/stdc++.h>
using namespace std;
int a[101];
int f1[101];
int f2[101];
int main()
{
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        f1[i]=1;
        f2[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j])
            {
                f1[i]=max(f1[i],f1[j]+1);
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>i;j--)
        {
            if(a[i]>a[j])
            {
                f2[i]=max(f2[i],f2[j]+1);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,f2[i]+f1[i]-1);
    }
    printf("%d",n-ans);
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int a[200],b[200],c[200];
int n,maxx;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=1;
        for(int j=1;j<=i-1;j++)
        {
            if(a[i]>a[j]&&b[j]+1>b[i])
            {
                b[i]=b[j]+1;
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        c[i]=1;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[i]&&c[j]+1>c[i])
            {
                c[i]=c[j]+1;
            }
        }
    }
    maxx=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]+c[i]>maxx)
        {
            maxx=b[i]+c[i];
        }
    }
    cout<<n-maxx+1<<endl;
    return 0;
}

这不就是正向+反向取最长上升子序列。
结束。

#include<bits/stdc++.h>
using namespace std;
#define MAX 105
int a[MAX],b[MAX],c[MAX];
int main()
{
    int n,i,j,maxx;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
    {
        b[i]=1;
        for(j=1;j<=i-1;j++)
        {
            if(a[i]>a[j]&&b[j]+1>b[i])
                b[i]=b[j]+1;
        }
    }
    for(i=n;i>=1;i--)
    {
        c[i]=1;
        for(j=i+1;j<=n;j++)
        {
            if(a[j]<a[i]&&c[j]+1>c[i])
            c[i]=c[j]+1;
        }
    }
    maxx=-1;
    for(i=1;i<=n;i++)
    {
        if(b[i]+c[i]>maxx)
            maxx=b[i]+c[i];
    }
    printf("%d",n-maxx+1);
    return 0;
}

单调序列变体

序列的正反向各做一次LIS，就能求出我们想要的队列形式的最优解了。
还是很好想的~

#include <iostream>
using namespace std;
int N;
int A[105];
int F[105], E[105];
void DP () {
    
    for(int i=2; i<=N; i++)
        for(int j=1; j<i; j++)
            if (A[i]>A[j]) 
                F[i]=max(F[i],F[j]+1);
    for(int i=N-1; i>=1; i--)
        for(int j=N; j>i; j--)
            if (A[i]>A[j]) 
                E[i]=max(E[i],E[j]+1);              
    return;
    
}
int main () {
    
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    DP();
    int ans=0;
    for(int i=1; i<=N; i++) 
        ans=max(ans, F[i]+E[i]+1);
    cout << N-ans;    
    
}

'''
    最讨厌抄代码了
    放个python3
    应该能读懂（解释详尽）
    vijos 上测的AC记录
                    Accepted
        #      状态           耗时   内存占用
        #1   Accepted   39ms    3.324 MiB
        #2   Accepted   33ms    3.508 MiB
        #3   Accepted   31ms    3.367 MiB
        #4   Accepted   30ms    3.492 MiB
        #5   Accepted   31ms    3.438 MiB
        #6   Accepted   30ms    3.367 MiB
        #7   Accepted   37ms    3.379 MiB
        #8   Accepted   35ms    3.367 MiB
        #9   Accepted   32ms    3.367 MiB
        #10  Accepted   31ms    3.465 MiB
'''
import re;
import sys;

#这几个你们不用管
def readmore():
    return map(int,sys.stdin.readline().split())
def read():
    return int(input())

def readarray():
    s = input()
    h = re.split(' ',s)
    l = [0,]
    for i in h:
        l.append(int(i))
    l.append(0)
    return l

n = read()#读入n
a = readarray()#读入a[1..n]

f1 = [0 for i in range(n+3)]#初始化 f1 表示a每个点的上升子序列
f2 = [0 for i in range(n+3)]#初始化 f2 表示a每个点的下降子序列

for i in range(1,n+1):#for i=1->n
    for j in range(0,i):#for j=0->i-1
        if a[j]<a[i]:
            f1[i] = max(f1[j]+1,f1[i])#求原点到每个点之中最长上升子序列
for i in range(n,0,-1):
    for j in range(i+1,n+2):
        if a[j]<a[i]:
            f2[i] = max(f2[j]+1,f2[i])#求每个点到结束点之中最长下降子序列
MAX = 0
for i in range(1,n+1):
    MAX = max (MAX,f1[i]+f2[i]-1)#算出最多可以多长（要减一）
print(n-MAX)#输出（记得是剔除的不是留下的）