hdu 1025&hdu 1025 LIS(O(n*n)和O(n*log(n)))两种解法 - c++编程基础

e I and poor ones marked from 1 to n are located in Line II.

The location of Rich City 1 is on the left of all other cities, Rich City 2 is on the left of all other cities excluding Rich City 1, Rich City 3 is on the right of Rich City 1 and Rich City 2 but on the left of all other cities ... And so as the poor ones.

But as you know, two crossed roads may cause a lot of traffic accident so JGShining has established a law to forbid constructing crossed roads.

For example, the roads in Figure I are forbidden.

In Z http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcmRlciB0byBidWlsZCBhcyBtYW55IHJvYWRzIGFzIHBvc3NpYmxlLCB0aGUgeW91bmcgYW5kIGhhbmRzb21lIGtpbmcgb2YgdGhlIGtpbmdkb20gLSBKR1NoaW5pbmcgbmVlZHMgeW91ciBoZWxwLCBwbGVhc2UgaGVscCBoaW0uIF5fXjxicj4KCgogCjxicj4KCklucHV0CgpFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBuKDEgodwgbiCh3CA1MDAsMDAwKS4gVGhlbiBuIGxpbmVzIGZvbGxvdy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBwIGFuZCByIHdoaWNoIHJlcHJlc2VudHMgdGhhdCBQb29yIENpdHkgcCBuZWVkcyB0byBpbXBvcnQgcmVzb3VyY2VzIGZyb20gUmljaCBDaXR5IHIuIFByb2Nlc3MgdG8gdGhlIGVuZCBvZiBmaWxlLjxicj4KCgogCjxicj4KCk91dHB1dAoKRm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgdGhlIHJlc3VsdCBpbiB0aGUgZm9ybSBvZiBzYW1wbGUuIDxicj4KWW91IHNob3VsZCB0ZWxsIEpHU2hpbmluZyB3aGF0"s the maximal number of road(s) can be built.

Sample Input

Sample Output

Case 1:
My king, at most 1 road can be built.

Case 2:
My king, at most 2 roads can be built.

Hint
Huge input, scanf is recommended.

hdu 1025 题目大意：找一个序列，使得这个序列的任意一个i 解题思路：先对a排个序，然后对b找一个LIS即可。这个题目的n有5*10^5，显然O（n*n）的算法会超时，可以在基础的算法上加上二分查找位置的思想，使得算法复杂度降低为O（n*log(n)），详见代码：
题目地址：Constructing Roads In JGShining's Kingdom
AC代码：

#include
              
               
#include
               
                 #include
                
                  using namespace std; struct node { int x; int y; }nod[500005]; int ans[500005]; int cmp(node a,node b) { return a.x
                 
                  >n) { for(i=0;i
                  
                   l+1) { mid=(l+r)>>1; if(ans[mid]
                   
                    =1;i--) if(ans[i]<1e6) { res=i; break; } printf("Case %d:\n",++cas); if(res>1) printf("My king, at most %d roads can be built.\n\n",res); else printf("My king, at most %d road can be built.\n\n",res); } return 0; } /* 2 1 2 2 1 3 1 2 2 3 3 1 5 2 2 3 3 4 1 1 4 5 5 */

还有一个题目，也是需要O（n*log(n)）的LIS的。 uva 10635Prince and Princess (LCS转LIS)
题目地址：Prince and Princess 解题思路：uva 10635Prince and Princess (LCS转LIS)

hdu 1025&hdu 1025 LIS(O(n*n)和O(n*log(n)))两种解法(二)

hdu 1025&hdu 1025 LIS(O(nn)和O(nlog(n)))两种解法(二)