Noip 2013花職人

花職人(flower.cpp/c/pas)【問題の説明】花職人棟棟には花が植えられていて、どの花にも高さがあります.花が長ければ長いほど、この列の一部の花を移し、残りをその場に残しておくことで、残りの花が空間的に成長することができ、残りの花が並ぶのとは異なります.具体的には、棟棟棟の花の高さは整数�.一部の花が残された花の高さを順に1,2,...,とすると、棟棟は以下の2つの条件のうち少なくとも1つが条件Aを満たすことを望んでいる:すべての�に対して、2�>2�−1、そして2�>2�+1;条件B:すべての�に対して、2�<2�−1、そして2�<2�+1.なお、上記の2つの条件は、�=1の場合に同時に満たされ、�>1の場合に最大1つ満たされる.すみません、棟棟は最大何本の花をその場に残すことができますか.
【入力】入力ファイルはflower.inです.入力された最初の行には、開始時の花の株数を表す整数が含まれています.2番目の行には、1、2、…、1株あたりの花の高さを表す整数が含まれています.
【出力】
出力ファイルはflowerです.out. 1行を出力し、1つの整数を含み、最大でその場に残る花の株数を表す.【入出力サンプル】flower.in 5 5 3 2 1 2 flower.out 3【入出力サンプル説明】3本の花をちょうど残すには、例えば、1、4、5本目を残し、高さはそれぞれ5、1、2で、条件Bを満たす方法がいくつかある.
【データ範囲】20%のデータに対して、≤10;30%のデータに対して、≤25;70%のデータに対して、≤1000、0≤ℎ�≤1000;100%のデータに対して、1≤

#include
#include
using namespace std;
const int maxn=100005;
int a[maxn];
int dp[maxn][2];
int main(){
    freopen("flower.in","r",stdin);
    freopen("flower.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        dp[i][0]=dp[i][1]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;jif(a[i]>a[j]) dp[i][0]=max(dp[j][1]+1,dp[i][0]);
            if(a[i]1]=max(dp[j][0]+1,dp[i][1]);
}
}
printf("%d",max(dp[n][0],dp[n][1]));
return 0;
}