HDU 1025 DP + 二分

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1025求最长递增子序列，O(n^2)的复杂度超时，需要优化为O(n*logn)f[i]存储长度为i的最小末尾#include<stdio.h>int poor[500010], f[500010];int main(){int n, k = 1;while (scanf("%d", &n) != EOF){int m, m1;for (int i = 0; i<n; i++){scanf("%d%d", &m, &m1);poor[m] = m1;}f[1] = poor[1];intlength = 1;for (i = 2; i<=n; i++){int low = 1;int high = length;while (low<=high)//二分{int mid = (low + high)/2;if (f[mid] < poor[i]) low = mid + 1;else high = mid - 1;}f[low] = poor[i];if (low > length) length ++;}printf("Case %d:\n", k ++);if (length == 1)printf("My king, at most 1 road can be built.\n\n");elseprintf("My king, at most %d roads can be built.\n\n",length); }return 0;}