題目描述
某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。
輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。
輸入輸出格式
輸入格式： 一行，若干個(gè)正整數(shù)最多100個(gè)。
輸出格式： 2行，每行一個(gè)整數(shù)，第一個(gè)數(shù)字表示這套系統(tǒng)最多能攔截多少導(dǎo)彈，第二個(gè)數(shù)字表示如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。
輸入輸出樣例
輸入樣例#1： 389 207 155 300 299 170 158 65 輸出樣例#1： 6 2
in: 181 205 471 782 1033 1058 1111 out: 1 7
第一問求最長不升子序列，第二問求最長上升子序列。 http://blog.csdn.net/acdreamers/article/details/7626671
#include<cstdio>#include<iostream>#include<cstring>using namespace std;int n,top,a[1001],d[1001];//d[i]表示長度為i的有序序列中末尾最小的數(shù) int binary1(int l,int r,int x){ if(l<=r) { int mid=(l+r)/2; if(x>d[mid]) binary1(l,mid,x); else {//x>= x=2:2 2 4 找見4, x=3:2 2 4找見4 if((x<d[mid] || x==d[mid]) && x>d[mid+1]) return mid+1; else binary1(mid+1,r,x); } }}int binary2(int l,int r,int x){ if(l<=r) { int mid=(l+r)/2; if(x==d[mid])return mid; else if(x<d[mid]) binary2(l,mid-1,x); else { if(x<d[mid+1]) return mid+1; else binary2(mid+1,r,x); } }}int main(){ scanf("%d",&a[1]); top=1,d[top]=a[1]; int i=2; while(scanf("%d",&a[i])==1) { if(a[i]<=d[top]) d[++top]=a[i]; else{ if(a[i]>d[1]) d[1]=a[i]; else d[binary1(1,top,a[i])]=a[i];// } i++; } cout<<top<<endl; int len=--i; memset(d,0,sizeof d); top=1,d[top]=a[1]; for(int i=2;i<=len;i++) { if(a[i]>d[top]) d[++top]=a[i]; else{ if(a[i]<d[1]) d[1]=a[i]; else d[binary2(1,top,a[i])]=a[i];// } } cout<<top<<endl;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
