/*

【例4】拦截×××(Noip1999提高组第1题--DP+贪心)

某国为了防御敌国的×××袭击，发展出一种×××拦截系统。但是这种×××拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的×××来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的×××。

输入×××依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，×××数不超过1000），计算这套系统最多能拦截多少×××，如果要拦截所有×××最少要配备多少套这种×××拦截系统。样例：INPUT 389 207 155 300 299 170 158 65

OUTPUT

6（最多能拦截的×××数）--DP2（拦截所有×××最少要配的系统数）---贪心

*/

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int main(){ freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);

int i,j,k,x,n,maxx,m,a[10000],b[10000],h[10000];i=1;n=0;m=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(h,0,sizeof(h));while (cin>>a[i]){    maxx=0;    //计算前i-1个×××最佳拦截的方案    for (j=1;j<=i-1;j++)       {        if (a[j]>=a[i])        if (b[j]>maxx)            maxx=b[j];    }                 b[i]=maxx+1;    if (b[i]>m) m=b[i];    x=0;    //计算由哪一套系统拦截×××    for (k=1;k<=n;k++)                         if (h[k]>=a[i])         if (x==0) x=k;        //如果有多套系统可拦截，则选择上一次拦截高度最低的        else if (h[k]

}