以下是我的代码：
#include<stdio.h>
int max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int a[102],len_1[101]/**//*下降序列*/,len_2[101]/**//*上升序列*/,tot[101],n,i,j,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
{
len_1[i]=1;
len_2[i]=1;
}
for(i=n;i>=1;i--)
for(j=i+1;j<=n;j++)
if(a[i]>a[j])//以 i 为头最长下降序列
len_1[i]=max(len_1[j]+1,len_1[i]);
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(a[i]<a[j])//以 i 为尾最长上升序列
len_2[j]=max(len_2[i]+1,len_2[j]);
/**//*
for(i=1;i<=n;i++)
printf("%d ",len_1[i]);
putchar('\n');
for(i=1;i<=n;i++)
printf("%d ",len_2[i]);
putchar('\n');
//*/
for(i=1;i<=n;i++)
tot[i]=len_1[i]+len_2[i];
ans=0;
for(i=1;i<=n;i++)
ans=max(ans,tot[i]);
printf("%d\n",n-ans+1);
return 0;
}
posted on 2010-01-06 19:13
lee1r 阅读(560)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：动态规划