题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1025
题意:河两岸各有n各点,编号从左到右都依次为1~n, 已知它们与对岸某点能先连,若不能相交,最多能连几点。
仔细分析题目,可以联系到LIS。
因为数据量较大,所以用LIS的Nlog(N)的方法做。
LIS算法详细讲解见:http://www.wutianqi.com/?p=1850
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include <iostream> using namespace std; int p[500005], b[500005]; int n; int bSearch(int num, int k) { int low=1, high=k; while(low<=high) { int mid=(low+high)/2; if(num>=b[mid]) low=mid+1; else high=mid-1; } return low; } int LIS() { int low = 1, high = n; int k = 1; b[1] = p[1]; for(int i=2; i<=n; ++i) { if(p[i]>=b[k]) b[++k] = p[i]; else { int pos = bSearch(p[i], k); b[pos] = p[i]; } } return k; } int main() { int a, b; int nCases = 1; while(scanf("%d", &n) != EOF) { for(int i=1; i<=n; ++i) { scanf("%d %d", &a, &b); p[a] = b; } int ans = LIS(); printf("Case %d:\nMy king, at most %d road", nCases++, ans); if(ans != 1) printf("s"); printf(" can be built.\n\n"); } return 0; } |
来的稍晚了一下。
呵呵,有kita在,十个沙发有九个要被她抢到。
搶沙花…然後…吃pasta去…
意大利面?
對啊,各種意大利面
=。=
我也想吃。