【例4】ブロック×××(『情報学オリンピック一本通』)

/*【例4】ブロック×××(Noip 1999向上グループ第1題--DP+欲張り)https://www.luogu.org/problemnew/show/P1020https://www.luogu.org/problemnew/show/P1158
ある国は敵国を防衛するために×××襲い掛かる×××ブロッキングシステム.でもこの×××遮断システムには欠陥がある:その最初の砲弾は任意の高さに達することができるが、その後、各砲弾は前の砲弾の高さを上回ることができない.ある日、レーダーが敵国の×××襲来する.このシステムはまだ試用段階にあるため、1つのシステムしかないため、すべてのシステムをブロックできない可能性があります.×××.入力×××順次飛来する高さ(レーダーが与える高さデータは30000以下の正の整数であり、×××数は1000を超えない)、このシステムがどれだけブロックできるかを計算します.×××,すべてを止めるなら×××少なくとも何セットは必要ですか?×××ブロッキングシステム.サンプル:INPUT 389 207 155300 299 170 15865
OUTPUT 6(最大ブロック可能なもの×××数)--DP 2(すべてブロック)×××最低限必要なシステム数)---欲張り
*/#include#include#includeusing 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]

}