第一篇博客,想想还有些小激动。
使用LIS,最长递增子序列,导弹打的高度是递减的,如果在序列中出现了递增,那么说明我们需要另外一套系统来打这个递增的高度,也就是出现了多少次的递增,我们就需要多少套系统。求出最长递增子序列就是结果。
#include <stdio.h> #define MAX 30050 #define CMP(A, B) ((A) > (B)) int n, num[MAX], len_min[MAX]; int BinarySearch(int a, int b, int k) { int mid; while (a < b) if (CMP(k, len_min[mid = (a + b) >> 1])) a = mid + 1; else b = mid; return a; } int LIS(void) { int a = 0, b = 0, k; int i; for (i = 0; i < n; i++) { if (len_min[k = BinarySearch(a, b - 1, num[i])] >= num[i]) len_min[k] = num[i]; else len_min[b++] = num[i]; } return b; } int main(void) { int i; while (~scanf("%d", &n)) { for (i = 0; i < n; i++) scanf("%d", &num[i]); printf("%d\n", LIS()); } return 0; }