挺水的
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n,f[101],a[101],f1[101];
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
memset(f,0,sizeof(f));
memset(f1,0,sizeof(f1));
f[n]=1;
for (int i=n-1;i>=1;i--)
{
f[i]=1;
for (int j=i+1;j<=n;j++)
if (a[i]>a[j])
if (f[j]+1>f[i]) f[i]=f[j]+1;
}
f1[1]=1;
for (int i=2;i<=n;i++)
{
f1[i]=1;
for (int j=i-1;j>=1;j--)
if (a[i]>a[j])
if (f1[j]+1>f1[i])f1[i]=f1[j]+1;
}
int max=0;
for (int i=1;i<=n;i++)
if (f[i]+f1[i]-1>max)max=f[i]+f1[i]-1;
cout<<n-max;
}

program d;
var
a:array[0..120]of longint;
b:array[1..120]of longint;
i,j,n,ma,z,ma2,ma3,ma4:longint;
begin
readln(n);
for i:=1 to n do
begin
read(b[i]);
end;
ma4:=0;
for i:=1 to n do
begin
a[i]:=0;ma2:=0;ma3:=0;
if i>1 then
for j:=i-1 downto 1 do
begin
ma:=-666;
for z:=j+1 to i do
if (b[j]<b[z])and(a[z]>ma) then
begin
ma:=a[z];
end;
a[j]:=ma+1;
if a[j]>ma2 then ma2:=a[j];
end;
if i<n then
for j:=i+1 to n do
begin
ma:=-666;
for z:=j-1 downto i do
if (b[j]<b[z])and(a[z]>ma) then
begin
ma:=a[z];
end;
a[j]:=ma+1;
if a[j]>ma3 then ma3:=a[j];
end;
if ma2+ma3+1>ma4 then ma4:=ma2+ma3+1;
end;
write(n-ma4);
end.

灰常简单的动态规划，由于N不大，没有做优化的必要，
计算一个**最长递增序列**和一个**最长递减序列**即可

#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    int t[110];
    for (int i = 1; i <= n; i++) { cin >> t[i]; }  // for

    int finc[110];  // Increasing sequence
    int fdec[110];  // Decreasing sequence
    memset(finc, 0, sizeof(finc));
    memset(fdec, 0, sizeof(fdec));

    // Compute LIS
    finc[1] = 1;
    for (int i = 2; i <= n; i++) {
        int max = 0;

        for (int j = 1; j < i; j++) {
            if (t[j] < t[i] and max < finc[j]) { max = finc[j]; }
        }

        finc[i] = max + 1;
    }  // for

    // Compute LDS
    fdec[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        int max = 0;

        for (int j = n; j > i; j--) {
            if (t[j] < t[i] and max < fdec[j]) { max = fdec[j]; }
        }  // for

        fdec[i] = max + 1;
    }  // for

    int m = INT_MAX;
    for (int i = 1; i <= n; i++) {
        int k = finc[i] + fdec[i] - 1;
        if (n - k < m) { m = n - k; }
    }  // for

    cout << m;

    return 0;
}  // function main

一道锻炼思维的水题，不过我WA了多次，就是错在底下注释的两处，策不清的童鞋可以想想为什么……

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 524 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 528 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 528 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 532 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 528 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 528 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 524 KiB, score = 10
测试数据 #8: Accepted, time = 3 ms, mem = 528 KiB, score = 10
测试数据 #9: Accepted, time = 2 ms, mem = 528 KiB, score = 10
Accepted, time = 5 ms, mem = 532 KiB, score = 100
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int team[110],a[110];
int l[110],r[110];
int ans,cnt;

int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
cnt=1;
for(int i=1;i<=n;i++){
int k=cnt;
while(888){
if(team[k-1]<a[i]){
l[i]=max(l[i-1],k);//这里必须取MAX
team[k]=a[i];
break;
}
k--;
}
cnt=max(cnt,k+1);
}
cnt=1;
for(int i=n;i>=1;i--){
int k=cnt;
while(888){
if(team[k-1]<a[i]){
r[i]=max(r[i+1],k);//这里必须取MAX
team[k]=a[i];
break;
}
k--;
}
cnt=max(cnt,k+1);
}

for(int i=1;i<n;i++)
ans=max(ans,l[i]+r[i+1]);
printf("%d\n",n-ans);
return 0;
}

/*

author: Slience_K
Belong: C++
Pro: Vijos P 1098

*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n , ans , f[ 105 ][ 2 ] , a[ 105 ];
int main(){
freopen( "P1098.in" , "r" , stdin );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ )
scanf( "%d" , &a[ i ] );
f[ 1 ][ 0 ] = 1;
for( int i = 2 ; i <= n ; i++ ){
for( int j = 1 ; j < i ; j++ )
if ( a[ i ] > a[ j ] ) f[ i ][ 0 ] = max( f[ i ][ 0 ] , f[ j ][ 0 ] + 1 );
if ( !f[ i ][ 0 ] ) f[ i ][ 0 ] = 1;
}
f[ n ][ 1 ] = 1;
for( int i = n - 1 ; i >= 1 ; i-- ){
for( int j = i + 1 ; j <= n ; j++ )
if ( a[ i ] > a[ j ] ) f[ i ][ 1 ] = max( f[ i ][ 1 ] , f[ j ][ 1 ] + 1 );
if ( !f[ i ][ 1 ] ) f[ i ][ 1 ] = 1;
}
for( int i = 1 ; i <= n ; i++ )
ans = max( ans , f[ i ][ 0 ] + f[ i ][ 1 ] - 1 );
printf( "%d" , n - ans );
return 0;
}

手残把最长上升序列写错了，wa3次啊啊啊啊啊
``#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100+5;
int a[maxn]={0},n;

int dp(int k) {
int d[maxn]={0};
int ans1=1;
for (int i=1;i<=k;++i) {
d[i]=1;
for (int j=1;j<i;++j) {
if (a[j]<a[i]) {
d[i]=max(d[i],d[j]+1);
}
}
ans1=max(ans1,d[i]);
}
int ans2=1;
int f[maxn]={0};
for (int i=k;i<=n;++i) {
f[i]=1;
for (int j=k;j<i;++j) {
if (a[j]>a[i]) {
f[i]=max(f[i],f[j]+1);
}
}
ans2=max(ans2,f[i]);
}
return n-ans1-ans2+1;
}

int main() {
ios::sync_with_stdio(0);
cin>>n;
for (int i=1;i<=n;++i) cin>>a[i];
int ans=(1<<30);
for (int i=1;i<=n;++i) {
ans=min(ans,dp(i));
}
cout<<ans;
return 0;
}``

测试数据 #0: Accepted, time = 312 ms, mem = 952 KiB, score = 10

测试数据 #1: Accepted, time = 1 ms, mem = 508 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 508 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 556 KiB, score = 10

测试数据 #4: Accepted, time = 16 ms, mem = 512 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 516 KiB, score = 10

测试数据 #6: Accepted, time = 640 ms, mem = 1224 KiB, score = 10

测试数据 #7: Accepted, time = 203 ms, mem = 884 KiB, score = 10

测试数据 #8: Accepted, time = 203 ms, mem = 900 KiB, score = 10

测试数据 #9: Accepted, time = 437 ms, mem = 1092 KiB, score = 10

Accepted, time = 1827 ms, mem = 1224 KiB, score = 100

虽说AC了不过这结果，咳咳……

在这里给大家提供一种不使用动态规划的解法（一定意义上的暴搜）：

用结构体List（为了不与STL里的混淆将首字母大写）表示排成的队列，用last和length分别表示该队列最后一人的身高和队列的长度

然后设立两个集合set<List>：up和down，如果队列的后半部分已经开始按降序排列，则将这个队列放入down中，否则放入up中

先把第一个人放入up中，然后逐个检查两个集合中的队列，如果可以在末端加上当前这个人，则将新的队列放入相应的集合（注意保留原队列），利用set自带的去重机制可以方便地合并等效的队列

最后求出两个集合中队列的最长长度Lmax，总人数N-Lmax即为所求答案

理论上down集合可以进行优化，不过鄙人语言基础比较渣只实现了第一条……
设立worse（List A,List B）函数，检查A队列是否比B队列“更差”
1、如果待加入down的队列temp比down中的某一个队列“更差”，则temp不能加入
2、如果down中的某个队列比temp“更差”，则从down中去掉这个队列（这个鄙人不太会写……）

代码：

#include <cstdio>
#include <set>
using namespace std;
struct List
{
int last,length;
List(int a,int b) {
this->last=a;this->length=b;}
};
bool operator < (const List& A,const List& B)
{
if(A.last==B.last && A.length==B.length) return false;
return true;
}
bool worse(List A,List B)
{
return (A.last<=B.last && A.length<=B.length);
}
int main()
{
set<List> up,down;
int N,height,prev;scanf("%d %d",&N,&height);up.insert(List(height,1));prev=height;
for(int k=2;k<=N;k++)
{
scanf("%d",&height);
if(height!=prev)
{
prev=height;
for(set<List>::iterator i=up.begin();i!=up.end();i++)
{
if(height>(*i).last)
up.insert(List(height,(*i).length+1));
else if(height<(*i).last)
{
List temp(height,(*i).length+1);bool ok=true;
for(set<List>::iterator j=down.begin();j!=down.end();j++)
{
if(worse(temp,*j)) {ok=false;break;}
}
if(ok) down.insert(temp);
}
}
up.insert(List(height,1));
for(set<List>::iterator j=down.begin();j!=down.end();j++)
{
if(height<(*j).last) down.insert(List(height,(*j).length+1));
}
}
}
int maximum=0;
for(set<List>::iterator i=up.begin();i!=up.end();i++)
if((*i).length>maximum) maximum=(*i).length;
for(set<List>::iterator j=down.begin();j!=down.end();j++)
if((*j).length>maximum) maximum=(*j).length;
printf("%d",N-maximum);
return 0;
}

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

int num[500];
int f1[500],f2[500];

int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin>>num[i];
int ans=0;
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(num[i] > num[j])
f1[i] = max(f1[i],f1[j]+1);
for(int i=n; i>=1; i--)
for(int j=n; j>i; j--)
if(num[i] > num[j])
f2[i] = max(f2[i],f2[j]+1);
for(int i=1; i<=n; i++)
ans = max(ans , f1[i]+f2[i]);

cout<<n-ans+1;
system("pause");
return 0;
}

菜鸟WA了15次才过，错因是注释的那一句话，有跟我一样的吗

#include<stdio.h>

//不可以只从头到尾搜一遍确定最长序列，因为减掉某些部分后可能出现更长序列

int main( )
{
int n,a[101]={0},max,i,j,up[101],down[101];

scanf("%d",&n);

for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
up[i]=1;
down[i]=1;
}

for(i=2;i<=n;i++)
{
for(j=i;j>=1;j--)
if(a[j]<a[i] && up[j]+1>up[i]) up[i]=up[j]+1;
}

for(i=n-1;i>=1;i--)
{
for(j=i;j<=n;j++)
if(a[j]<a[i] && down[j]+1>down[i]) down[i]=down[j]+1;
}

max=up[1]+down[1];

for(i=1;i<=n;i++)

if (up[i]+down[i]>max) max=up[i]+down[i];

printf("%d",n-max+1);

return 0;
}

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

正反2便不下降子序列（是这个吧）然后加起来-1（中间的重复计算了一次）中的最大值就是答案。

block code

program P1098;
uses math;
var a,b,data:array[0..100] of longint;
i,n,t,ans,j,sum:longint;
begin
read(n); ans:=999999; for i:=1 to n do a[i]:=0; for i:=1 to n do b[i]:=0;
for i:=1 to n do
read(data[i]);

for i:=n downto 1 do
begin
for j:=i to n do
if data[i]>data[j] then
a[i]:=max(a[j]+1,a[i]);

if a[i]=0 then a[i]:=1;
end;

for i:=1 to n do
begin
for j:=i downto 1 do
if data[i]>data[j] then
b[i]:=max(b[j]+1,b[i]);

if b[i]=0 then b[i]:=1;
end;

for i:=1 to n do
begin
sum:=a[i]+b[i]-1; sum:=n-sum; if sum<ans then ans:=sum;
end;

write(ans);
end.

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 816 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 816 KiB, score = 10

测试数据 #2: Accepted, time = 7 ms, mem = 812 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 816 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #7: Accepted, time = 3 ms, mem = 816 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 812 KiB, score = 10

测试数据 #9: Accepted, time = 0 ms, mem = 816 KiB, score = 10

Accepted, time = 10 ms, mem = 816 KiB, score = 100

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

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

#include <cstdio>
#include <algorithm>

#define M 1000

using namespace std;

int dp1[M],dp2[M],t[M],n,imax;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
dp1[i] = 1;dp2[i] = 1;
}
dp1[0] = 0;dp1[1] = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++) {
if(t[i]>t[j]&&dp1[j]+1>dp1[i]) dp1[i] = dp1[j]+1;
}
dp2[0] = 0;dp2[1] = 1;
for(int i = n-1; i >= 1; i--)
for(int j = n; j > i; j--) {
if(t[i]>t[j]&&dp2[j]+1>dp2[i]) dp2[i] = dp2[j]+1;
}
imax = 0;
for(int i = 1; i <= n; i++) {
if(dp1[i]+dp2[i]>imax) imax = dp1[i] + dp2[i];
}
printf("%d",n - imax + 1);
}

###Block code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<fstream>
using namespace std;
const int maxn=101;
int d[maxn][4],o,ans=9999999,i,j,maxm,temp,max1,max2,n;

void lis(int t,int h)
{
if(t==h)
{d[t][2]=1;
d[t][3]=0;}
else
{
maxm=0;
temp=0;
for(j=t+1;j<=h;j++)
{
if(d[j][2]>maxm&&d[j][1]>d[t][1]) {maxm=d[j][2]; temp=j;}
}
d[t][2]=d[temp][2]+1;
d[t][3]=temp;
}
}
void llis(int t,int h)
{
if(t==h)
{d[t][2]=1;
d[t][3]=0;}
else
{
maxm=0;
temp=0;
for(j=t+1;j<=h;j++)
{
if(d[j][2]>maxm&&d[j][1]<d[t][1]) {maxm=d[j][2]; temp=j;}
}
d[t][2]=d[temp][2]+1;
d[t][3]=temp;
}
}

int main()
{
cin>>n;
for(i=1;i<=n;i++) cin>>d[i][1];
for(o=2;o<=n-1;o++)
{
for(i=o;i>=1;i--) lis(i,o);
for(i=n;i>=o+1;i--) llis(i,n);
max1=max2=0;
for(i=1;i<=o;i++) if(d[i][2]>max1) max1=d[i][2];
for(i=o+1;i<=n;i++) if(d[i][2]>max2) max2=d[i][2];
if(n-max1-max2<ans) ans=n-max1-max2;
}
cout<<ans;
return 0;
}

求解，哪里错了
#include<iostream>
using namespace std;
const int MAX=100;
int dp[MAX],tall[MAX];
int i,j,ti,n;
int lis()
{
int max,ans=0;
dp[1]=1;
for(i=2;i<=n;i++)
{
max=0;
for(j=1;j<i;j++)
{
if(dp[j]>max&&tall[j]<tall[i])
{
max=dp[j];
}
dp[i]=max+1;
}
if(ans<dp[i])
{
ans=dp[i];
ti=i;
}
}

return ans;
}
int lus(int s)
{
int max,ans=0;
for(i=1;i<=n;i++)dp[i]=0;
dp[1]=1;
for(i=n;i>=s;i--)
{
max=0;
for(j=n-1;j<i;j--)
{
if(dp[j]>max&&tall[j]>tall[i])
{
max=dp[j];
}
dp[i]=max+1;
}
if(ans<dp[i])
{
ans=dp[i];
}
}
return ans;
}

int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>tall[i];
}
cout<<n-lis()-lus(ti)+1<<endl;
return 0;
}

#include<cstring>
#include<iostream>
using namespace std;
main()
{
int a[200],b[200],c[200],n,i,j,max=0;
cin>>n;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)
cin>>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;
}
for(i=1;i<=n;i++)
if(b[i]+c[i]>max)
max=b[i]+c[i];
cout<<n-max+1;
}

这么水的题竟然还wa了……血的教训：记得f2[n]的初始化！或者循环时就从n或1开始
var
f1,f2,a:array[0..1000]of longint;
i,j,n,max:longint;

begin
readln(n);
for i:=1 to n do
read(a[i]);
fillchar(f1,sizeof(f1),0);
fillchar(f2,sizeof(f2),0);
f1[1]:=1;
f2[1]:=1;
for i:=2 to n do begin
f1[i]:=1;
for j:=i downto 1 do
if (a[j]<a[i]) and (f1[j]+1>f1[i]) then
f1[i]:=f1[j]+1;
end;
for i:=n downto 1 do begin
f2[i]:=1;
for j:=i+1 to n do
if (a[j]<a[i]) and (f2[j]+1>f2[i]) then
f2[i]:=f2[j]+1;
end;
max:=0;
for i:=1 to n do
if f1[i]+f2[i]>max then max:=f1[i]+f2[i];
writeln(n-max+1);
readln;
readln;
end.

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

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步