有疑问请看：http://hi.baidu.com/bgfumsjefublmtd/item/034656b0f669d473ba0e12a4

var
i,j,n,ans:longint;
a,b,c,d,e:array[1..1000] of longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
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[j]<a[i]) and (b[j]+1>b[i]) then b[i]:=b[j]+1;

for i:=2 to n do
for j:=i-1 downto 1 do
if (a[j]<a[i]) and (c[j]+1>c[i]) then c[i]:=c[j]+1;

for i:=1 to n do
begin
d[i]:=b[i]+c[i];
if d[i]>ans then ans:=d[i];
end;
writeln(n-ans+1);
end.

正着找一遍，倒着再找一遍。

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 544 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 544 KiB, score = 10
Accepted, time = 0 ms, mem = 544 KiB, score = 100
代码
#include<cstdio>
#include<algorithm>
int n,h[101],a[101],b[101],r=0;
int main(){
scanf("%d",&n);
for (int i=1; i<=n; i++) a[i]=b[i]=1;
for (int i=1; i<=n; i++) scanf("%d",&h[i]);
for (int i=1; i< n; i++)
for (int j=0; j< i; j++) {
if (h[1+i]>h[1+j]) a[1+i]=std::max(a[1+i],a[1+j]+1);
if (h[n-i]>h[n-j]) b[n-i]=std::max(b[n-i],b[n-j]+1);
} for (int i=1; i<=n; i++)r=std::max(r , a[i]+b[i]-1);
printf("%d",n-r);
}

又A了一道 233
动归求解，算两遍最长不升子序列
var
a,b,c:array[0..300]of integer;
n,m,max,i,j:integer;
begin
readln(n);
for i:=1 to n do begin read(a[i]);b[i]:=1;c[i]:=1 end;
readln;
for i:=n-1 downto 1 do begin
m:=1;
for j:=i+1 to n do
if (a[j]<a[i])and (b[j]+1>m) then m:=b[j]+1;
b[i]:=m
end;
//这一遍倒着算
for i:=2 to n do begin
m:=1;
for j:=i-1 downto 1 do
if (a[j]<a[i])and(c[j]+1>m) then m:=c[j]+1;
c[i]:=m
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.

LIS+LDS
 
 

#include <iostream>
#include <fstream>

using namespace std;

const int MAX_SIZE = 100;

int a[MAX_SIZE + 1], f[MAX_SIZE + 1], g[MAX_SIZE + 1];

int main()
{
int N;
cin >> N;

int i, j, middle;
for (i = 1; i <= N; i++) {
cin >> a[i];
}

//
// 分别求解以i为中间点(1<=i<=N)时的1~i最长上升序列和i~N最长下降序列的长度和，并保存最小值
//
int ans, MaxAns = 0, maxLenA, maxLenB;
for (middle = 1; middle <= N; middle++) {
f[1] = 1;
for (i = 2; i <= middle; i++) {
f[i] = 1;
for (j = i - 1; j >= 1; j--) {
if (f[j] + 1 > f[i] && a[i] > a[j]) f[i] = f[j] + 1;
}
}
g[middle] = 1;
for (i = middle + 1; i <= N; i++) {
g[i] = 1;
for (j = i - 1; j >= middle; j--) {
if (g[j] + 1 > g[i] && a[i] < a[j]) g[i] = g[j] + 1;
}
}
maxLenA = maxLenB = 0;
for (i = 1; i <= middle; i++) {
if (f[i] > maxLenA)
maxLenA = f[i];
}
for (i = middle; i <= N; i++) {
if (g[i] > maxLenB)
maxLenB = g[i];
}
ans = maxLenA + maxLenB - 1;
if (ans > MaxAns) MaxAns = ans;
}

//
// 最少出队人数 = 总人数 - 最大保留人数(最长上升+最长下降)
//
cout << (N - MaxAns);

return 0;
}

//本人的虽然代码很渣，但容易明白。计算出符合规则的有多少人，然后总数减去符合规则的便是ans。
var
n,i,j,ans:longint;
f,g,h:array[1..200]of longint;
procedure init;
begin
readln(n);
for i:=1 to n do
begin
read(h[i]);
f[i]:=1;g[i]:=1;
end;
end;

procedure dpone;
begin
for i:=1 to n-1 do
for j:=i+1 to n do
if (h[i]<h[j]) and (f[i]>=f[j]) then f[j]:=f[i]+1;
end;

procedure dptwo;
begin
for i:=n downto 2 do
for j:=i-1 downto 1 do
if (h[i]<h[j]) and (g[i]>=g[j]) then g[j]:=g[i]+1;

end;

procedure print;
begin
ans:=0;
for i:=1 to n do
if ans<f[i]+g[i] then ans:=f[i]+g[i];
ans:=n-ans+1;
writeln(ans);
end;

begin
init;
dpone;
dptwo;
print;
end.

uses math;
var a,up,down:array[1..100] of longint;
n,i,j,m,len:longint;
begin
m:=0;
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do up[i]:=1;
for i:=1 to n do down[i]:=1;
for i:=2 to n do
begin
len:=0;
for j:=i downto 1 do
if (a[j]<a[i])and(up[j]>len) then len:=up[j];
if len>0 then up[i]:=len+1;
end;
for i:=n-1 downto 1 do
begin
len:=0;
for j:=i to n do
if (a[j]<a[i])and(down[j]>len) then len:=down[j];
if len>0 then down[i]:=len+1;
end;
for i:=1 to n do
m:=max(m,up[i]+down[i]-1);
writeln(n-m);
end.

'uses math;
var a,up,down:array[1..100] of longint;
n,i,j,m,len:longint;
begin
m:=0;
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do up[i]:=1;
for i:=1 to n do down[i]:=1;
for i:=2 to n do
begin
len:=0;
for j:=i downto 1 do
if (a[j]<a[i])and(up[j]>len) then len:=up[j];
if len>0 then up[i]:=len+1;
end;
for i:=n-1 downto 1 do
begin
len:=0;
for j:=i to n do
if (a[j]<a[i])and(down[j]>len) then len:=down[j];
if len>0 then down[i]:=len+1;
end;
for i:=1 to n do
m:=max(m,up[i]+down[i]-1);
writeln(n-m);
end.'

###Block code
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100

int a[maxn+1],b[maxn+1],f[maxn+1],g[maxn+1],n;

using namespace std;

int main()
{
int i,j,k,t,y,maxx;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[n-i+1]=a[i];
}
f[0]=0;
for(i=1;i<=n;i++)
{
maxx=0;
for(j=0;j<i;j++)
if(a[j]<a[i]&&maxx<f[j]+1)maxx=f[j]+1;
f[i]=maxx;
}
g[0]=0;
for(i=1;i<=n;i++)
{
maxx=0;
for(j=0;j<i;j++)
if(b[j]<b[i]&&maxx<g[j]+1)maxx=g[j]+1;
g[j]=maxx;
}
maxx=0;
for(i=1;i<=n;i++)
if(maxx<f[i]+g[n-i+1]-1)maxx=f[i]+g[n-i+1]-1;
printf("%d\n",n-maxx);

}
return 0;
}

###code blocks
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100

int a[maxn+1],b[maxn+1],f[maxn+1],g[maxn+1],n;

using namespace std;

int main()
{
int i,j,k,t,y,maxx;
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[n-i+1]=a[i];
}
f[0]=0;
for(i=1;i<=n;i++)
{
maxx=0;
for(j=0;j<i;j++)
if(a[j]<a[i]&&maxx<f[j]+1)maxx=f[j]+1;
f[i]=maxx;
}
g[0]=0;
for(i=1;i<=n;i++)
{
maxx=0;
for(j=0;j<i;j++)
if(b[j]<b[i]&&maxx<g[j]+1)maxx=g[j]+1;
g[j]=maxx;
}
maxx=0;
for(i=1;i<=n;i++)
if(maxx<f[i]+g[n-i+1]-1)maxx=f[i]+g[n-i+1]-1;
printf("%d\n",n-maxx);

}
return 0;
}

=.=
话说这道题难度为3？！

=.= 好久不写 竟然忘了初始化Orz
Var n,i,m,ans:longint;
a:array[1..1000] of longint;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Function dijian(x:longint):longint;
Var f:array[1..1000] of longint;
i,j:longint;
Begin
For i:=1 to n do f[i]:=1;
For i:=n-1 downto 1 do
For j:=i+1 to n do
If a[j]<a[i] then f[i]:=max(f[i],f[j]+1);
Exit(f[x]);
End;
Function dizeng(x:longint):longint;
Var f:array[1..1000] of longint;
i,j:longint;
Begin
For i:=1 to n do f[i]:=1;
For i:=2 to n do
For j:=1 to i do
If a[j]<a[i] then f[i]:=max(f[i],f[j]+1);
Exit(f[x]);
End;
Begin
readln(n);
For i:=1 to n do read(a[i]);
For i:=1 to n do ans:=max(ans,dizeng(i)+dijian(i)-1);
writeln(n-ans);
readln;
End.

###Block code
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define __max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
#define inf 0x7f//2147483647
#define iinf 0x7fffffff
#define PI acos(-1.0)
#define NOBUG puts("No_Bug_Hear");
#define STOP system("pause");
#define FOUT freopen("out.txt","w",stdout);
#define FIN freopen("in.txt","r",stdin);
#define OUTCLOSE fclose(stdout);
#define INCLOSE fclose(stdin);
#define INIT(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int lf[111],rt[111],tmax,f[111],n;
int main(){
//FIN
//FOUT
while(cin>>n){
rep(i,0,n){
lf[i]=rt[i]=1;
cin>>f[i];
}
rep(i,0,n){
rep(j,0,i)
if(f[i]>f[j])
lf[i]=max(lf[i],lf[j]+1);
}
for(int i=n-1;i>-1;i--){
for(int j=n-1;j>i;j--)
if(f[i]>f[j])
rt[i]=__max(rt[i],rt[j]+1);
}
tmax=-1;
rep(i,0,n)
tmax=__max(tmax,rt[i]+lf[i]-1);
cout<<n-tmax<<endl;
}
//INCLOSE
//OUTCLOSE
return 0;
}

#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define __max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
#define inf 0x7f//2147483647
#define iinf 0x7fffffff
#define PI acos(-1.0)
#define NOBUG puts("No_Bug_Hear");
#define STOP system("pause");
#define FOUT freopen("out.txt","w",stdout);
#define FIN freopen("in.txt","r",stdin);
#define OUTCLOSE fclose(stdout);
#define INCLOSE fclose(stdin);
#define INIT(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int lf[111],rt[111],tmax,f[111],n;
int main(){
//FIN
//FOUT
while(cin>>n){
rep(i,0,n){
lf[i]=rt[i]=1;
cin>>f[i];
}
rep(i,0,n){
rep(j,0,i)
if(f[i]>f[j])
lf[i]=max(lf[i],lf[j]+1);
}
for(int i=n-1;i>-1;i--){
for(int j=n-1;j>i;j--)
if(f[i]>f[j])
rt[i]=__max(rt[i],rt[j]+1);
}
tmax=-1;
rep(i,0,n)
tmax=__max(tmax,rt[i]+lf[i]-1);
cout<<n-tmax<<endl;
}
//INCLOSE
//OUTCLOSE
return 0;
}

program p1098;
var i,j,m,k,lb,n,w:longint;
a,b,c,d:array[0..200]of longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
lb:=1;
b[1]:=1;
c[1]:=1;
for i:=2 to n do
begin
j:=1;
while(a[b[j]]>=a[i])and(j<=lb)do
inc(j);
if j>lb then
begin
c[i]:=1;
inc(lb);
b[lb]:=i;
end
else
begin
c[i]:=c[b[j]]+1;
w:=1;
while c[i]<c[b[w]] do inc(w);
for k:=lb downto w do b[k+1]:=b[k];
b[w]:=i;
inc(lb);
end;
end;
fillchar(b,sizeof(b),0);
lb:=1;
b[1]:=n;
d[n]:=1;
for i:=n-1 downto 1 do
begin
j:=1;
while(a[b[j]]>=a[i])and(j<=lb)do inc(j);
if j>lb then
begin
d[i]:=1;
inc(lb);
b[lb]:=i;
end
else
begin
d[i]:=d[b[j]]+1;
w:=1;
while d[i]<d[b[w]] do inc(w);
for k:=lb downto w do b[k+1]:=b[k];
b[w]:=i;
inc(lb);
end;
end;
m:=0;
for i:=1 to n do
if m<c[i]+d[i]-1 then m:=c[i]+d[i]-1;
write(n-m);
end.

噗。。错了好多次，真的要想好再写啊，不然真的悲剧了
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 110;

void solve(int *num, int dp[], int n){
for(int i = 1;i <= n;i++){

int Max = -1,loc = i;

for(int j = 1;j < i;j++)

if(num[i] > num[j]&&dp[j] > Max){

loc = j;

Max = dp[j];

}

dp[i] = dp[loc] + 1;

}

}

int main(){
int n, i, num1[N], num2[N], inc[N], dec[N];
while(~scanf("%d", &n)){
memset(inc, 0, sizeof(inc));
memset(dec, 0, sizeof(dec));
for(i = 1;i <= n;i++){
scanf("%d", &num1[i]);
num2[i] = num1[i];
}
std::reverse(num2 + 1, num2 + n + 1);//翻转数组 即1 2 3变成3 2 1
solve(num1, inc, n);
solve(num2, dec, n);
int res = 10000;
for(i = 1;i <= n;i++)
res = std::min(res, n - (inc[i] + dec[n - i + 1] - 1));
printf("%d\n", res);
}
return 0;
}

点击查看程序源码+详细题解

(⊙v⊙)嗯。。(⊙v⊙)嗯。。。我就是将其看做两组最长上升子序列b，c，循环顶点，再将其比较~

代码！

program xxg;

var

n,i,j,k,mix:longint;

a,b,c:array[1..200]of longint;

begin

read(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do

begin

b[i]:=1;

for j:=1 to i-1 do

if (a[i]>a[j])and(b[j]+1>b[i]) then inc(b[i]);

end;

for i:=n downto 1 do

begin

c[i]:=1;

for j:=n downto i+1 do

if (a[i]>a[j])and(c[j]+1>c[i]) then inc(c[i]);

end;

for i:=1 to n do

if (b[i]+c[i])>mix then mix:=b[i]+c[i];

mix:=n-mix+1;

writeln(mix);

end.

是左搜一边，右搜一边。。。。。。。。。。

var

t:array[1..10000]of longint;

c,d,e,n:longint;

begin

read(n);

for c:=1to n do begin

read(t[c]);

if t[c]>t[c-1] then d:=c;

end;

c:=0;

for e:=1 to (d-1) do

if t[e]>=t[e+1] then c:=c+1;

for e:=d to n do

if t[e]

var n,i,j,max:longint;

a,c,d:array[1..1000] of longint;

begin

readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n do begin c[i]:=1;d[i]:=1;end;

for i:=1 to n do

begin

for j:=1 to i-1 do

if (a[j]