/*
若N個數 為遞增序列
則最多需要N個導彈系統貪心 + DP 見注釋
*/
#include <stdio.h>
#define MAX 100000
int height[MAX]; //height[i]表示第i個防導彈系統所能防御的最大高度
int t; //t個數
int high; //height[i]中 最高高度 的 下標
int a[MAX];
int main(){
int i,j; //j 導彈系統個數
while(scanf("%d",&t)!= EOF){
scanf("%d",&a[0]);
height[0] = a[0];
high = 0;
j = 1;
for(i = 1; i < t; i++){
scanf("%d",&a[i]);
if(a[i] >= height[high]){
height[j++] = a[i];
if(height[j - 1] > height[high]){ //更新high值
high = j - 1;
}
} else { //貪心選擇高度最小的且比能夠抵抗住a[i]的導彈
int k,min = 0X7FFFFFFF,min_index;
for(k = 0; k < j; k++){
if(height[k] >= a[i] && min > height[k] - a[i]){
min = height[k] - a[i];
min_index = k;
}
}
height[min_index] = a[i];
}
}
printf("%d\n",j);
}
return 0;
}

轉載于:https://www.cnblogs.com/lxf90/archive/2011/04/09/2010059.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 1257 最少拦截系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。