hdu 1257 最少攔截系統（貪心）

題意：

最少需要多少個攔截系統才能將所有的導彈攔截下來。

?

思路：

第1枚導彈一定需要第一個攔截系統，第2枚導彈如果比第1個高度高，則需要第二個攔截系統。

考慮第i枚導彈，如果前i-1枚導彈的高度都比它小，則需要新的一個攔截系統，否則一定只需要之前的某個攔截系統，不需要新開一個攔截系統。

原因是：假設最優方案中是為它新開了一個攔截系統，那么一定是之前的所有攔截系統都去攔截它后面的某些導彈去了，所以跳過了它。

而我們完全可以讓之前的某個攔截系統去攔截它，而新開的攔截系統去攔截后面的導彈。

所以證明了：不需要新開一個攔截系統，只要之前所在比它高度大的導彈。

那么要讓哪個攔截系統去攔截它呢？找到所有攔截系統中可以攔截它的并且最后一次攔截的高度是小的那個。這樣是最優的。

開一個數組記錄在最優的方案下每一個攔截系統最后一次攔截到的導彈高度。

看代碼。

?

代碼：

int n;
int h[100005];
int d[100005];int main(){while(scanf("%d",&n)!=EOF){rep(i,1,n) scanf("%d",&h[i]);d[1]=h[1];int nc=1;rep(i,2,n){if(h[i]>d[nc]){d[++nc]=h[i];}else{int pos=lower_bound(d+1,d+1+nc,h[i])-d;d[pos]=h[i];}}printf("%d\n",nc);}return 0;
}

?