#include<reg51.h>
sbit pluse=P1^0
main()
{
pluse=0
pluse=1
}
最长上升子序列（LIS）问题描述：设现在有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。
示例：1 7 3 5 9 4 8 结果为4
题例：参看POJ 2533
解法：
1. DP之O(n2)算法：先按DP的思想来分析一下，要想求n个数的最长上升子序列，设有数据数组data[n]和状态数组dp[n]，则对其尾元素data[n]来说，它的最长上升子序列就是它自己，即dp[n]=1，而当把它的前一个元素data[n-1]考虑进来时，如果data[n-1]<data[n]则会存在一个长度为2的上升子序列，如果data[n-1]>data[n]那么这个长度仍会是1。当把这个思想一般化的时候，对于任意一个元素data[k]来说，我们需要找出在data[k]以后的元素中比data[k]大，并且最长的一个序列做为它的后继。这样dp[k]就可以写成dp[k+1]+1。现在我们定义一个量dp[k]=m，它代表着到第k个元素为止（可以包含k也可以不包含k），它的最长上升序列的长度为m。仔细体会dp[k]=m的意义，这里面的k是可包括在内，也可以不包括在内的（与之前的最大子序列和不同）。要想确定这个m的值，就必须找到一个在第k个元素之前的一个元素的值小于data[k]的值，并且那个元素所对应的dp值是找到的满足第一个条件前提下dp值最大的一个。这就意味着我们需要内层遍历之前算出来的dp值，所以需要两层循环来实现这个算法。这样我们就可以总结出状态转移方程为dp[k]=max(dp[i](1<=i<=k&&a[i]<a[k])+1。其中找dp[i]的过程我们需要用一层循环来实现，而找dp[k]的过程也要一层循环，所以我们得到了O(n2)的算法。
dp[k]=max(dp[i])+1 其中i满足(1<=i<=k&&a[i]<a[k])
例程：
#include <stdio.h>
const int inf = -0x3fffffff
int main(void)
{
int i,j,len,max,res,data[] = {1,7,3,5,9,4,8},dp[20]={1}
len = sizeof(data)/sizeof(int)
res = max = inf
for(i=1i<leni++)
{
max = inf
for(j=0j<=ij++)
if(data[i]>data[j]&&max<dp[j])
max=dp[j]
dp[i]=max+1
if(res<dp[i])
res = dp[i]
}
printf("%d\n",res)
return 0
}
你是理工的吧#include<stdio.h>
const int MAX=105
int down[MAX],up[MAX]
int h[MAX],n
void get_up()
{
int i,tmp,j
for(i=0i<ni++)
{
tmp=1
for(j=i-1j>=0j--)
{
if(h[i]>h[j]&&up[j]+1>tmp)
tmp=up[j]+1
}
up[i]=tmp
}
}
void get_down()
{
int i,j,tmp
for(i=n-1i>=0i--)
{
tmp=1
for(j=i+1j<nj++)
{
if(h[i]>h[j]&&down[j]+1>tmp)
tmp=down[j]+1
}
down[i]=tmp
}
}
int main()
{
int i,max
while(scanf("%d",&n)!=EOF)
{
for(i=0i<ni++)
scanf("%d",&h[i])
get_up()
get_down()
max=0
for(i=0i<ni++)
{
if(up[i]+down[i]-1>max)
max=up[i]+down[i]-1
}
printf("%d\n",n-max)
}
return 0
}
